LeetCode Hot 100：多维动态规划

LeetCode Hot 100：多维动态规划

62. 不同路径

思路 1：动态规划

class Solution {
public:
    int uniquePaths(int m, int n) {
        if (m == 1 || n == 1)
            return 1;
		
		// dp[i][j]: 到达 (i,j) 的不同路径数
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        // 初始化
        for (int i = 1; i <= m; i++)
            dp[i][1] = 1;
        for (int j = 1; j <= n; j++)
            dp[1][j] = 1;
        // 状态转移
        for (int i = 2; i <= m; i++)
            for (int j = 2; j <= n; j++)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

        return dp[m][n];
    }
};

思路 2：组合数学

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return comb(m + n - 2, n - 1)

64. 最小路径和

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        if (grid.empty())
            return 0;

        int m = grid.size(), n = m ? grid[0].size() : 0;
        // dp[i][j]: 到达 (i,j) 的最小路径和
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        // 初始化
        for (int i = 1; i <= m; i++)
            dp[i][1] = dp[i - 1][1] + grid[i - 1][0];
        for (int j = 1; j <= n; j++)
            dp[1][j] = dp[1][j - 1] + grid[0][j - 1];
        // 状态转移
        for (int i = 2; i <= m; i++)
            for (int j = 2; j <= n; j++) {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }

        return dp[m][n];
    }
};

5. 最长回文子串

class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        // 特判
        if (n < 2)
            return s;

        int maxLen = 1, begin = 0;
        // dp[i][j]: s[i...j] 是否是回文串
        vector<vector<int>> dp(n, vector<int>(n, false));
        // 初始化：所有长度为 1 的子串都是回文串
        for (int i = 0; i < n; i++)
            dp[i][i] = true;
        // 状态转移
        for (int len = 2; len <= n; len++) // 枚举子串长度
            for (int i = 0; i < n; i++)    // 枚举左边界
            {
                int j = i + len - 1; // 计算右边界
                if (j >= n)          // 右边界越界
                    break;
                if (s[i] != s[j])
                    dp[i][j] = false;
                else {
                    if (len <= 3)
                        dp[i][j] = true;
                    else
                        dp[i][j] = dp[i + 1][j - 1];
                }
                if (dp[i][j] == true && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    begin = i;
                }
            }
        
        return s.substr(begin, maxLen);
    }
};

1143. 最长公共子序列

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        if (text1.empty() || text2.empty())
            return 0;

        int m = text1.length(), n = text2.length();
        // dp[i][j] : text1[0,...,i) 和 text2[0,...,j) 最长公共子序列的长度
        vector<vector<int>> dp(m + 1, vector(n + 1, 0));
        // 状态转移
        for (int i = 1; i <= m; i++)
            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];
    }
};

72. 编辑距离

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.length(), n = word2.length();
        // 特判
        if (word1.empty())
            return n;
        if (word2.empty())
            return m;

        // dp[i,j]: 使 word1[0...,i) == word2[0,...,j) 的最少编辑次数
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        // 初始化
        for (int i = 0; i <= m; i++)
            dp[i][0] = i;
        for (int j = 0; 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 - 1][j - 1], dp[i][j - 1], dp[i - 1][j]}) + 1;
            }

        return dp[m][n];
    }
};