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];
}
};
标签:return,string,int,Solution,Hot,vector,100,LeetCode,dp
From: https://blog.csdn.net/ProgramNovice/article/details/143271162