动态规划--(不同的子序列,编辑距离，两个字符串的删除)

代码随想录day56 动态规划模块 不同的子序列,编辑距离，两个字符串的删除

1.leetcode 115. 不同的子序列

1.1思路及详细步骤

  按照动态规划的做题步骤来分析

   1.确定dp数组以及下标的含义

dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。

   2. 确定递推公式

s[i - 1] 与 t[j - 1]相等
s[i - 1] 与 t[j - 1] 不相等
当s[i - 1] 与 t[j - 1]相等时，dp[i][j]可以有两部分组成。
一部分是用s[i - 1]来匹配，那么个数为dp[i - 1][j - 1]。
一部分是不用s[i - 1]来匹配，个数为dp[i - 1][j]

  3. dp数组的初始化问题

那么dp[i][0]一定都是1，

  4.确定遍历顺序

从前往后的遍历两层

  5.推导dp数组

1.2 代码示例

class Solution {
    public int numDistinct(String s, String t) {
     int[][] dp=new int[s.length()+1][t.length()+1];
     for(int i=0;i<=s.length();i++){
         dp[i][0]=1;
     }
    // for(int i=0;i<=t.length();i++){
    //      dp[0][i]=1;
    //  }
     for(int i=1;i<=s.length();i++){
         for(int j=1;j<=t.length();j++){
             if(s.charAt(i-1) == t.charAt(j-1)){
                 dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
             }else{
                 dp[i][j]=dp[i-1][j];
             }
         }
     }
     return dp[s.length()][t.length()];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

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

2.1思路及详细步骤

  直接用最大子序和的方法做 点这里

2.2 代码示例

class Solution {
    public int minDistance(String word1, String word2) {
       int[][] dp=new int[word1.length()+1][word2.length()+1];

            for (int i = 1; i <= word1.length(); i++) {

              for (int j = 1; j <= word2.length(); j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j]=dp[i-1][j-1]+1;
                } else {
                    dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
       return word1.length()+word2.length()-2*dp[word1.length()][word2.length()];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

3.leetcode 72. 编辑距离

3.1思路及详细步骤

  按照动态规划的做题步骤来分析

   1.确定dp数组以及下标的含义

dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。

   2. 确定递推公式

if (word1[i - 1] == word2[j - 1])
不操作
if (word1[i - 1] != word2[j - 1])
增
删
换
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 - 1][j], dp[i][j - 1]}) + 1;
}

  3. dp数组的初始化问题

for (int i = 0; i <= word1.size(); i++) dp[i][0] = i;
for (int j = 0; j <= word2.size(); j++) dp[0][j] = j;

  4.确定遍历顺序

从前往后的遍历两层

  5.推导dp数组

3.2 代码示例

class Solution {
    public int minDistance(String word1, String word2) {
       int[][] dp=new int[word1.length()+1][word2.length()+1];
    for (int i = 1; i <= word1.length(); i++) {
        dp[i][0] =  i;
    }
    for (int j = 1; j <= word2.length(); j++) {
        dp[0][j] = j;
    }
            for (int i = 1; i <= word1.length(); i++) {

              for (int j = 1; j <= word2.length(); j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j]=dp[i-1][j-1];
                } else {
                     dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j])+1;
                }
            }
        }
       return dp[word1.length()][word2.length()] ;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22