力扣 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 range
        for (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 pointer
        vector<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) // 右边界 j
            for (int i = 0; i < j; ++i) // 左边界 i
                if (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;
                else
                    dp[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] + 1

if (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];
    }
};