力扣 hot100 -- 多维动态规划

👇woc，这不是最熟悉那种，记忆化 dfs 或者 普通的深度优先搜索？？都适用于二维地图👇

DFS（深度优先搜索）8种题型_dfs典型问题-CSDN博客

目录

🥃不同路径

🌼最小路径和

🌼最长回文子串

AC  中心扩散

AC  动态规划

🐙最长公共子序列

🎂编辑距离

---

🥃不同路径

62. 不同路径 - 力扣（LeetCode）

“只能向下 或 向右”（注意限制条件）

注意二维vector的初始化，也可以直接用数组

/*
dp[i][j] : 到达(i, j)的路径数
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 每个点只来自于上边和左边
初始化 : dp[i][0] = 1, dp[][j] = 1
*/
class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m, vector<int>(n, 0)); // m行, 每一行 n 个元素for (int j = 0; j < n; ++j) dp[0][j] = 1; // 第一行初始化for (int i = 0; i < m; ++i)dp[i][0] = 1; // 第一列初始化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];}
};

🌼最小路径和

64. 最小路径和 - 力扣（LeetCode）

“只能向下 或 向右”（注意限制条件）

和上一题初始化不同，上一条是不同路径，本题是最小路径和

/*
dp[i][j] : 到达(i, j)的最小路径和
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
初始化 : dp[0][0], 然后从 (0,0) 开始，分别向右向下初始化第 0 行，第 0 列
*/
class Solution {
public:int minPathSum(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();vector<vector<int>> dp(m, vector<int>(n, 0));dp[0][0] = grid[0][0];for (int j = 1; j < n; ++j)dp[0][j] = dp[0][j - 1] + grid[0][j]; // 第 0 行for (int i = 1; i < m; ++i)dp[i][0] = dp[i - 1][0] + grid[i][0]; // 第 0 列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];}
};

🌼最长回文子串

5. 最长回文子串 - 力扣（LeetCode）

AC  中心扩散

遍历每一个字母，以这个字母为中心往外扩散，先找到以此为中心全部相同的字母

（比如 acdbbd 中的 bb），然后同时开始左右扩散，l - 1, r + 1，直到遇到左右边界不相等的字母（d == d，后面就不相等了，所以最长回文子串是 dbbd）

时间 O(n^2)

class Solution {
public:string longestPalindrome(string s) {int l = 0, r = 0, maxLen = 1; // 初始化 l, r 防止一个元素 out of rangefor (int i = 0; i < s.size(); ++i) {int left = i - 1, right = i + 1, len = 1; // len 当前长度// 左边 == s[i] 的while (left >= 0 && s[left] == s[i]) {left--;len++; }// 右边 == s[i] 的while (right < s.size() & s[right] == s[i]) {right++;len++;}// 左右同时扩展while (left >= 0 && right < s.size() && s[left] == s[right]) left--, right++, len += 2;if (len > maxLen) {maxLen = len;l = left + 1, r = right - 1; // 最长子串区间 [l, r]}}return s.substr(l, r - l + 1);}
};

AC  动态规划

中心扩散会有大量重复计算，比如 abbacd，第一个 b 已经计算过的回文串，第二个 b 还会重新计算，而 dp 能将计算过的状态记住，个别情况接近 O(n)

代码写完后，貌似没有发现时间上的优化，似乎都是差不多的

时间 O(n^2)

/*
dp[i][j] : 子串 [i, j] 区间是否回文
dp[i][j] = (dp[i+1][j-1] || j - i == 1) && (s[i] == s[j])
初始化 : dp[i][i] = 1 
*/
class Solution {
public:string longestPalindrome(string s) {int maxLen = 1, l = 0, r = 0, n = s.size();// 记得初始化 vector, 正确分配内存, 不然报错 null pointervector<vector<int>> dp(n, vector<int>(n, 0));for (int i = 0; i < n; ++i)dp[i][i] = 1;for (int j = 1; j < n; ++j) // 右边界 jfor (int i = 0; i < j; ++i) // 左边界 iif (s[i] == s[j] && (dp[i + 1][j - 1] || j - i == 1)) {dp[i][j] = 1;if (j - i + 1 > maxLen)maxLen = j - i + 1, l = i, r = j;}return s.substr(l, r - l + 1);}
};

🐙最长公共子序列

1143. 最长公共子序列 - 力扣（LeetCode）

dp[][] 下标从 1 开始，就不用初始化那么麻烦，也就是 dp[1][1] = 1，表示 text1[0] == text2[0]

/*
dp[i][j] : s1的[0, i-1] 和 s2的[0, j-1] 的最长公共子序列
if (s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1] + 1
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
初始化 : dp[0][0] = 0 OR 1
*/
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {int m = text1.size(), n = text2.size();vector<vector<int>> dp(m+1, vector<int>(n+1, 0));for (int i = 1; i <= m; ++i) // dp[][] 下标从 1 开始for (int j = 1; j <= n; ++j) {if (text1[i-1] == text2[j-1])dp[i][j] = dp[i-1][j-1] + 1;elsedp[i][j] = max(dp[i-1][j], dp[i][j-1]);}return dp[m][n];}
};// a c b q d b b q     
// a c d q

🎂编辑距离

72. 编辑距离 - 力扣（LeetCode）

1）类似上一题，dp[][] 下标从 1 开始，避免了麻烦的初始化，因为递推式有 [i-1][j-1], [i][j-1],

[i-1][j] 三种组合（下标改 1 开始后，<= m   <= n）

2）增删改的递推式中，+1不一定正确，所以要取 增 删 改 的最小值

3）初始化，观察递推式，都是根据 左，上，左上 三个方位得到的，所以初始化第一行和第一列

/*
dp[i][j] : s1 前 i 个字符 --> s2 前 j 个字符（下标 1 开始）递推式: dp[i][j] = ...
（取增删改，三者的最小值，作为新的 dp[i][j]）s1 增加1个变 s2: dp[i][j-1] + 1
s1 删除1个变 s2: dp[i-1][j] + 1
s1 替换1个变 s2: dp[i-1][j-1] + 1if (s1[i] == s2[j]) dp[i-1][j-1]
*/
class Solution {
public:int minDistance(string word1, string word2) {int m = word1.size(), n = word2.size();vector<vector<int>> dp(m+1, vector<int>(n+1, 0));// 初始化for (int i = 1; i <= m; ++i)dp[i][0] = i; // 第一列for (int j = 1; j <= n; ++j)dp[0][j] = j; // 第一行for (int i = 1; i <= m; ++i)for (int j = 1; j <= n; ++j) {if (word1[i-1] == word2[j-1])dp[i][j] = dp[i - 1][j - 1]; // 不用操作else // 增删改的最小值dp[i][j] = min(dp[i][j-1], min(dp[i-1][j], dp[i-1][j-1])) + 1;}return dp[m][n];}
};