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;elsedp[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;elsedp[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];elsedp[i][j] = min({dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]}) + 1;}return dp[m][n];}
};
