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] 中，也就是右下角的位置。
- 对于每一行 i（从第二行开始），我们依次更新每一列 j。更新的方式是根据左边的 dp[j-1] 和上面的 dp[j] 来计算当前格子的路径数：
具体实现代码（详解版）：
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) O(n2)
- 空间复杂度： O ( n 2 ) O(n^2) O(n2)
思路分析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(n^2) o(n2)
- 空间复杂度： O ( 1 ) O(1) 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()];
}
};
参考文章：代码随想录