代码随想录day45dp12

115.不同的子序列

题目链接
文章讲解

class Solution {
public:int numDistinct(string s, string t) {int m = s.size();  // 获取字符串 s 的长度int n = t.size();  // 获取字符串 t 的长度// 创建一个大小为 (m+1) x (n+1) 的 DP 数组，初始化为 0// dp[i][j] 表示 s 的前 i 个字符中，t 的前 j 个字符的不同子序列的个数vector<vector<unsigned long long>> dp(m + 1, vector<unsigned long long>(n + 1, 0));// 初始化：当 t 为空时，s 中任何一个子序列都是一个有效的子序列// 所以 dp[i][0] = 1（空字符串 t 的所有子序列都是 1）for (int i = 0; i <= m; i++) {dp[i][0] = 1;  // 空字符串 t 的所有子序列数都是 1}// 填充 dp 数组for (int i = 1; i <= m; i++) {  // 遍历 s 的字符for (int j = 1; j <= n; j++) {  // 遍历 t 的字符if (s[i - 1] == t[j - 1]) {// 如果当前字符相等，分为两种情况：// 1. 将 s[i-1] 加入子序列，增加 dp[i-1][j-1]；// 2. 不将 s[i-1] 加入子序列，继承 dp[i-1][j]。dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];} else {// 如果当前字符不同，只能不选择 s[i-1]，继承 dp[i-1][j]dp[i][j] = dp[i - 1][j];}}}// 返回 dp[m][n]，即 s 的前 m 个字符中，t 的前 n 个字符的不同子序列个数return dp[m][n];}
};

583. 两个字符串的删除操作

题目链接
文章讲解

class Solution {
public:int minDistance(string word1, string word2) {int m = word1.size();int n = word2.size();// 1. dp[i][j] 表示将 word1 的前 i 个字符和 word2 的前 j 个字符变得相同，最少需要的删除步数vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));// 2. 初始化：// 当 word2 是空串时，把 word1 的前 i 个字符全部删除，步数为 ifor (int i = 0; i <= m; i++) dp[i][0] = i;// 当 word1 是空串时，把 word2 的前 j 个字符全部删除，步数为 jfor (int j = 0; j <= n; j++) dp[0][j] = j;// 3. 状态转移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 {// 否则：删除 word1[i-1] 或 word2[j-1]，取最小值 + 1 步dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;}}}// 4. 答案是将两个字符串都处理完的最少删除步数return dp[m][n];}
};

72. 编辑距离

题目链接
文章讲解

class Solution {
public:int minDistance(string word1, string word2) {int m = word1.size();int n = word2.size();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]+1,dp[i-1][j]+1);dp[i][j]=min(dp[i][j],dp[i][j-1]+1);}}}return dp[m][n];}
};

体会：做dp问题的时候如果递推公式很难推出来， 在确定dp数组和如何初始化的前提下，我们可以画表根据自己理解填数字，然后再想一下这个是怎么根据前面状态推导过来的，这样递推表达式就很好写出来了。