动态规划 | part12

115. 不同的子序列 - 力扣（LeetCode）

给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）

题目数据保证答案符合 32 位带符号整数范围。

提示：

• 0 <= s.length, t.length <= 1000
• s 和 t 由英文字母组成

public int numDistinct(String s, String t) { int[][] dp = new int[s.length() + 1][t.length() + 1]; for (int i = 0; i < s.length() + 1; i++) { dp[i][0] = 1; } for (int i = 1; i < s.length() + 1; i++) { for (int j = 1; j < t.length() + 1; 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()]; }

解题：

• 子序列：通过删除（或不删除）原字符串中的某些字符而不改变剩余字符相对位置所组成的新字符串。

dp[i][j]的含义：字符串s的前i个字符（即s[0...i-1]）中，包含字符串t的前j个字符（即t[0...j-1]）作为子序列的个数。

为什么长度要 +1？

• • 为了处理空字符串的情况。
  • i=0表示s为空串。
  • j=0表示t为空串。

初始化：当t为空字符串（j=0）时，无论s是什么（包括s也是空串），t都是s的一个子序列（即“空串是任何字符串的子序列”）。结果：只有一种匹配方式（就是什么都不选），所以初始化为1。注：dp[0][j](其中 j>0) 默认初始化为 0

递归公式：

情况 1：当前字符匹配 (s[i-1] == t[j-1])

例如：s当前是'b',t当前也是'b'。

我们有两种选择：

使用这个字符进行匹配：如果用了s的这个字符去匹配t的这个字符，那么问题就变成了“在s的前i-1个字符中找t的前j-1个字符”。方案数为dp[i-1][j-1]。

不使用这个字符进行匹配：即使字符相同，我们也可以选择不使用s当前的这个字符，而是指望s前面的字符来完成对t的匹配。方案数为dp[i-1][j]。

结论：总方案数 = 两者之和。

dp[i][j]=dp[i−1][j−1]+dp[i−1][j]dp[i][j]=dp[i−1][j−1]+dp[i−1][j]

情况 2：当前字符不匹配 (s[i-1] != t[j-1])

例如：s当前是'a',t当前是'b'。

s的这个字符显然无法用来匹配t的当前字符。

我们只能忽略s的当前字符，去s的前面部分找t。

结论：方案数继承自上一行。

dp[i][j]=dp[i−1][j]

583. 两个字符串的删除操作 - 力扣（LeetCode）

给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

示例：

• 输入: "sea", "eat"
• 输出: 2
• 解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"

public int minDistance(String word1, String word2) { int[][] dp = new int[word1.length() + 1][word2.length() + 1]; for (int i = 0; i <= word1.length(); i++) { dp[i][0] = i; } for (int i = 0; i <= word2.length(); i++) { dp[0][i] = i; } 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(dp[i - 1][j], dp[i][j - 1]) + 1; } } } return dp[word1.length()][word2.length()]; }

解题：

匹配的情况下就不需要增加，直接继承状态即可。而不匹配的时候，我们需要进行删除元素，我们要从二者中取最小的，同时加1.

72. 编辑距离 - 力扣（LeetCode）

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符
• 示例 1：
• 输入：word1 = "horse", word2 = "ros"
• 输出：3
• 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')
• 示例 2：
• 输入：word1 = "intention", word2 = "execution"
• 输出：5
• 解释： intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u')

提示：

• 0 <= word1.length, word2.length <= 500
• word1 和 word2 由小写英文字母组成

public int minDistance(String word1, String word2) { int[][] dp = new int[word1.length() + 1][word2.length() + 1]; for (int i = 0; i <= word1.length(); i++) { dp[i][0] = i; } for (int i = 0; i <= word2.length(); i++) { dp[0][i] = i; } 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(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1; } } } return dp[word1.length()][word2.length()]; }

解题：

其余逻辑都很像前面的那些题目，区别在于不匹配的时候，不匹配的时候，有三种操作，插入，删除，或者替换，前俩者都需要看i-1或者j-1这俩个字符，而替换操作是看左上角位置。

Math.min(dp[i - 1][j],Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;