LeetCode 热题100 之 多维动态规划

1.不同路径

思路分析：动规五部曲

• dp数组定义：dp[i][j]表示从起点（0，0）到位置(i,j)的路径数量
• 递推公式：dp[i][j] = dp[i-1][j] + dp[i][j-1]
  • 从 (i-1, j) 位置到 (i, j) 需要走一步向下的路径。
  • 从 (i, j-1) 位置到 (i, j) 需要走一步向右的路径。
  • 所以，当前格子 (i, j) 的路径总数等于其上方和左方的路径数之和。
• 初始化方式：
  • 因为递推公式里面的状态要依赖于上一行和上一列的状态，所以开始应该初始化第一行和第一列。
  • 在第一行上，dp[0][j] = 1（所有位置均为 1）。因为从 (0, 0) 到 (0, j) 只能通过向右的路径到达，即没有选择，只能一路往右走。
  • 在第一列上，dp[i][0] = 1（所有位置均为 1）。因为从 (0, 0) 到 (i, 0) 只能通过向下的路径到达，即没有选择，只能一路往下走。
• 遍历顺序：
  • 遍历每一行
  • 遍历每一列
• 打印dp数组：最后应该返回dp[m - 1][n - 1];

具体实现代码（详解版）：

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 0));  // 初始化 dp 数组

        // 初始化第一行和第一列
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][0] = 1;  // 第一行
                dp[0][j] = 1;  // 第一列
            }
        }

        // 根据递推公式填充 dp 数组
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];  // 递推公式
            }
        }

        return dp[m - 1][n - 1];  // 返回右下角的路径数
    }
};

优化：在这个问题中，我们可以观察到每一行的 dp 数组的计算只依赖于当前行和上一行的值。因此，我们只需要存储当前行和上一行的值，而不需要存储整个二维数组。

• 我们只需要一个一维数组 dp 来保存当前行的计算结果，并用一个临时数组保存上一行的结果。
• 每次计算新的行时，我们只需要根据上一行的值和当前行的值来更新 dp 数组，因此可以将二维 dp 数组压缩为一维。
• 递推关系
  • 对于每一行 i（从第二行开始），我们依次更新每一列 j。更新的方式是根据左边的 dp[j-1] 和上面的 dp[j] 来计算当前格子的路径数：
    dp[j] = dp[j] + dp[j-1]。
  • 当所有的行都遍历完毕，最终的结果会存储在 dp[n-1] 中，也就是右下角的位置。

具体实现代码（详解版）：

class Solution {
public:
    int uniquePaths(int m, int n) {
        // 创建一个一维 dp 数组，用来存储当前行的路径数
        vector<int> dp(n, 1);  // 初始化第一行为 1

        // 从第二行开始计算
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // dp[j] 存储的是上一行的 dp[j]，dp[j-1] 存储的是上一行的 dp[j-1]
                dp[j] = dp[j] + dp[j - 1];  // 更新当前行的 dp[j]
            }
        }

        // 最终的结果存储在 dp[n-1] 中，表示右下角的路径数
        return dp[n - 1];
    }
};

2.最小路径和

思路分析：动规五部曲

• dp数组定义：dp[i][j]表示从左上角 (0, 0) 到达位置 (i, j) 的路径的最小路径和
• 递推公式
  • 每个位置 (i, j) 的最小路径和可以通过选择从上方或左方到达 (i, j) 的路径中的较小者，再加上当前格子的值 grid[i][j] 来获得。
  • 的·因此，递推公式为：dp[i][j]=grid[i][j]+min(dp[i−1][j],dp[i][j−1])；
  • 特殊情况：当 i == 0 或 j == 0 时，只能从左边或上边到达 (i, j)，需要单独处理。
• 初始化
  • dp[0][0] = 0;
  • 第一行和第一列只能从左到右或从上到下移动，因此可以逐步累加初始化。
• 遍历顺序：
  • 遍历每一行
  • 遍历每一列
• 打印dp数组：返回dp[m - 1][n - 1]即可。

这里特别要注意初始化的时候，具体来说，第一行和第一列的初始化应该在外部循环中进行，而不仅仅是在两个内部循环中。否则会导致每次进入 j 循环时都会重新赋值，这会导致结果错误。

具体实现代码（详解版）：

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        vector<vector<int>> dp(m, vector<int>(n, 0));  // 初始化 dp 数组
        dp[0][0] = grid[0][0];  // 起始点赋值

        // 初始化第一行
        for (int j = 1; j < n; ++j) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];  // 第一行只能从左边来
        }

        // 初始化第一列
        for (int i = 1; i < m; ++i) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];  // 第一列只能从上面来
        }

        // 动态规划填充 dp 表
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];  // 选择上方或左方的最小路径和
            }
        }

        return dp[m - 1][n - 1];  // 返回右下角的最小路径和
    }
};

优化：当前的算法空间复杂度是 O(m * n)，因为我们使用了一个二维数组 dp 来存储每个位置的最小路径和。实际上，计算每个位置的最小路径和时，只需要用到当前行和上一行的结果，因此可以将 dp 数组优化为一维数组，从而将空间复杂度降到 O(n)。

• 用一个一维数组 dp[j] 来表示当前行的最小路径和。每次更新时，我们从左到右依次计算当前行的值，每一列的最小路径和都只依赖于当前列和上一列的值。
• 使用 dp[j] 表示当前行的值，而上一行的结果会被覆盖。所以在计算时，只需要 dp[j] 和 dp[j-1] 来更新当前的最小路径和。
• 递推公式：dp[j] = min(dp[j], dp[j - 1]) + grid[i][j];
• 初始化：
  • dp[0] 初始化为 grid[0][0]，表示从起点开始的最小路径和。
  • 初始化第一行

具体实现代码（详解版）：

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        
        // 使用一个一维数组来表示每一行的最小路径和
        vector<int> dp(n, 0);
        
        // 初始化第一行
        dp[0] = grid[0][0];  // dp[0]表示第一行第一个位置的最小路径和
        for (int j = 1; j < n; ++j) {
            dp[j] = dp[j - 1] + grid[0][j];  // 第一行只能从左边来
        }

        // 更新后续行
        for (int i = 1; i < m; ++i) {
            dp[0] += grid[i][0];  // 第一列只能从上方来
            for (int j = 1; j < n; ++j) {
                dp[j] = min(dp[j], dp[j - 1]) + grid[i][j];  // 选择最小路径
            }
        }

        return dp[n - 1];  // 返回右下角的最小路径和
    }
};

3.最长回文字串

思路分析1：还是使用动态规划

• dp数组定义：表示从字符串 s[i…j] 是否是回文串
• dp数组更新
  • s[i] == s[j]：首先要判断子串的两端字符是否相同。
  • (j - i <= 1 || dp[i+1][j-1])：如果 i 和 j 相邻（即长度为2），或者子串 s[i+1…j-1] 是回文串，那么 s[i…j] 也一定是回文串。
  • 此时，dp[i][j] = true;
• 初始化：初始化时，所有的 dp[i][j] 默认值是 false。
• 遍历顺序：
  • 外层循环：i 从字符串的最后一位遍历到第一位，这样可以保证对于每一个位置，i 到 j 的子串已经根据先前的字符状态得到了正确的回文性。
  • 内层循环：j 从 i 开始遍历到字符串的最后一位，表示检查从 i 到 j 的子串。
• 更新最长回文字串的长度和内容
  • 每次找到一个回文子串时，更新 result，并且如果找到的回文子串长度大于当前的最长回文串，更新 str 为当前的回文子串。
• 返回结果：最后返回保存的最长回文子串str

dp[i][j] 需要满足两个条件：s[i] == s[j] 和 s[i+1…j-1] 是回文（或者子串长度为2）

具体实现代码（详解版）：

class Solution {
public:
   string longestPalindrome(string s) {
       // 定义一个二维dp数组，dp[i][j]表示子串s[i..j]是否是回文串
       vector<vector<int>> dp(s.size(), vector<int> (s.size(),false));
       
       int result = 0;  // 用于保存当前找到的最长回文串的长度
       string str;      // 用于保存最长回文子串

       // 从右到左遍历字符串s，外层循环是i从s.size()-1到0
       for(int i = s.size()-1; i >= 0; i--){ 
           // 内层循环是j从i到s.size()，遍历从i到j的子串
           for(int j = i; j < s.size(); j++){
               
               // 如果s[i] == s[j]，并且子串s[i+1..j-1]是回文串（或者i和j之间只有一个字符）
               if(s[i] == s[j] && (j-i <= 1 || dp[i+1][j-1])){
                   dp[i][j] = true;  // 将dp[i][j]设为true，表示s[i..j]是回文串
                   
                   // 更新最长回文串的长度result
                   result = max(result, j - i);
                   
                   // 如果当前子串长度大于result，更新最长回文子串str
                   if(j-i >= result) str = s.substr(i, j-i+1);
               }
           }
       }
       return str;  // 返回最长回文子串
   }
};

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n^2)$

思路分析2：中心扩展法

• 回文串的特性：回文串是对称的，因此我们可以从每个字符（或每对字符之间）出发，扩展到两边，检查是否满足回文的条件。
  • 单字符中心：例如“aba”，“b”是回文的中心，左右扩展。
  • 双字符中心：例如“abba”，两个字符之间“bb”是回文的中心，左右扩展。
• 对于每个字符 s[i]，我们考虑它作为回文的中心，分别向左和向右扩展，检查回文的长度。可以通过两种方式扩展。
• 每次扩展时，expandAroundCenter函数：这个辅助函数从给定的中心 left 和 right 开始，向两边扩展，直到遇到不匹配的字符为止。它返回扩展后的回文子串。记录当前找到的最长回文子串。
  • left-- 和 right++ 分别向左和向右扩展，直到左右字符不相等或者越界。
  • s.substr(left + 1, right - left - 1) 计算当前回文子串并返回。

具体实现代码（详解版）：

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty()) return "";
        
        int n = s.size();
        string result = "";
        
        // 中心扩展法
        for (int i = 0; i < n; i++) {
            // 1. 以 i 为中心，扩展回文串
            string odd = expandAroundCenter(s, i, i);
            // 2. 以 i 和 i+1 为中心，扩展回文串
            string even = expandAroundCenter(s, i, i + 1);
            
            // 更新最长回文子串
            if (odd.size() > result.size()) {
                result = odd;
            }
            if (even.size() > result.size()) {
                result = even;
            }
        }
        
        return result;
    }
    
    // 辅助函数，扩展回文串
    string expandAroundCenter(const string& s, int left, int right) {
        while (left >= 0 && right < s.size() && s[left] == s[right]) {
            left--;
            right++;
        }
        return s.substr(left + 1, right - left - 1);
    }
};

• 时间复杂度：$o(n^2)$
• 空间复杂度：$O(1)$

4.最长公共子序列

思路分析：动规五部曲

• dp数组定义：dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
• 递推公式：
  • 主要就是两大情况： text1[i - 1] 与 text2[j - 1]相同，text1[i - 1] 与 text2[j - 1]不相同
  • 如果text1[i - 1] 与 text2[j - 1]相同，那么找到了一个公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1;
  • 如果text1[i - 1] 与 text2[j - 1]不相同，那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取最大的。即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
• 初始化：test1[0, i-1]和空串的最长公共子序列自然是0，所以dp[i][0] = 0;同理dp[0][j]也是0。其他下标都是随着递推公式逐步覆盖，初始为多少都可以，那么就统一初始为0。
• 确定遍历顺序：从递推公式，可以看出，有三个方向可以推出dp[i][j]，那么为了在递推的过程中，这三个方向都是经过计算的数值，所以要从前向后，从上到下来遍历这个矩阵。
  -打印dp数组 ：dp[text1.size()][text2.size()]为最终结果

具体实现代码（详解版）：

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        // 定义一个二维 dp 数组，用于存储子问题的解
        // dp[i][j] 表示 text1[0...i-1] 和 text2[0...j-1] 的最长公共子序列的长度
        vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
        
        // 遍历 text1 和 text2
        for (int i = 1; i <= text1.size(); i++) {
            for (int j = 1; j <= text2.size(); j++) {
                // 如果 text1[i-1] == text2[j-1]，说明当前字符匹配
                if (text1[i - 1] == text2[j - 1]) {
                    // 在前一个状态 dp[i-1][j-1] 的基础上增加 1
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // 否则取前一个状态 dp[i-1][j] 或 dp[i][j-1] 中的较大值
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        // 最终的最长公共子序列长度为 dp[text1.size()][text2.size()]
        return dp[text1.size()][text2.size()];
    }
};

5.编辑距离

思路分析：动规五部曲

• dp数组定义：dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。
• 递推公式：dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。

if (word1[i - 1] == word2[j - 1])
    不操作
if (word1[i - 1] != word2[j - 1])
    增
    删
    换

• if (word1[i - 1] == word2[j - 1]) 那么说明不用任何编辑，dp[i][j] 就应该是 dp[i - 1][j - 1]，即dp[i][j] = dp[i - 1][j - 1];
  此时可能有同学有点不明白，为啥要即dp[i][j] = dp[i - 1][j - 1]呢？
  那么就在回顾上面讲过的dp[i][j]的定义，word1[i - 1] 与 word2[j - 1]相等了，那么就不用编辑了，以下标i-2为结尾的字符串word1和以下标j-2为结尾的字符串word2的最近编辑距离dp[i - 1][j - 1]就是 dp[i][j]了。
• if (word1[i - 1] != word2[j - 1])，此时就需要编辑了，如何编辑呢？

  • 操作一：word1删除一个元素，那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 再加上一个操作。
    即dp[i][j] = dp[i - 1][j] + 1;

  • 操作二：word2删除一个元素，那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 再加上一个操作。
    即dp[i][j] = dp[i][j - 1] + 1

  • word2添加一个元素，相当于word1删除一个元素，例如 word1 = “ad” ，word2 = “a”，word1删除元素’d’ 和 word2添加一个元素’d’，变成word1=“a”, word2=“ad”， 最终的操作数是一样！ dp数组如下图所示意的：

  • 操作三：替换元素，word1替换word1[i - 1]，使其与word2[j - 1]相同，此时不用增删加元素。那么只需要一次替换的操作，就可以让 word1[i - 1] 和 word2[j - 1] 相同。所以 dp[i][j] = dp[i - 1][j - 1] + 1;

  • 综上，当 if (word1[i - 1] != word2[j - 1]) 时取最小的，即：dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;

• 初始化
  • p[i][0] ：以下标i-1为结尾的字符串word1，和空字符串word2，最近编辑距离为dp[i][0]。那么dp[i][0]就应该是i，对word1里的元素全部做删除操作，即：dp[i][0] = i;同理dp[0][j] = j;
• 遍历顺序：
  • 我们从递推公式可以看出，dp[i][j]是依赖左上方、左边和上边元素的，所以在dp矩阵中一定是从左到右从上到下去遍历。
• 打印dp数组：最后返回dp[wors1.size()][word2.size()]就是我们所求的编辑距离。

具体实现代码（详解版）

class Solution {
public:
    int minDistance(string word1, string word2) {
        // 创建二维动态规划数组 dp，大小为 (word1.size() + 1) x (word2.size() + 1)
        // dp[i][j] 代表将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最小操作数
        vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));

        // 初始化 dp 数组的第一列：dp[i][0] 代表将 word1 的前 i 个字符转换为空字符串的操作数，即删除操作
        for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
        
        // 初始化 dp 数组的第一行：dp[0][j] 代表将空字符串转换为 word2 的前 j 个字符的操作数，即插入操作
        for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;

        // 从 dp[1][1] 开始填充整个 dp 数组
        for (int i = 1; i <= word1.size(); i++) {
            for (int j = 1; j <= word2.size(); j++) {
                // 如果 word1 的第 i 个字符与 word2 的第 j 个字符相同，不需要任何操作，直接继承上一个状态
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                }
                // 如果字符不同，则需要考虑三种操作：
                // 1. 删除 word1 的字符：dp[i - 1][j]
                // 2. 插入 word2 的字符：dp[i][j - 1]
                // 3. 替换 word1 的字符为 word2 的字符：dp[i - 1][j - 1]
                // 取三者的最小值，然后加 1，因为执行了一个操作（删除、插入或替换）
                else {
                    dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
                }
            }
        }

        // 返回最终的结果，dp[word1.size()][word2.size()] 即为将 word1 完全转换为 word2 所需的最小操作数
        return dp[word1.size()][word2.size()];
    }
};

参考文章：代码随想录

原文地址：https://blog.csdn.net/qq_43060884/article/details/143714259

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！