代码随想录算法训练营Day55|LC392 判断子序列LC115 不同的子序列LC583 两个字符串的删除操作

本文主要是介绍代码随想录算法训练营Day55|LC392 判断子序列LC115 不同的子序列LC583 两个字符串的删除操作，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一句话总结：115有点难想转移方程。

原题链接：392 判断子序列

题比较简单，dp方法不做一一分析，代码如下：

class Solution {public boolean isSubsequence(String s, String t) {int m = s.length(), n = t.length();int[][] dp = new int[m + 1][n + 1];for (int i = 1; i <= m; ++i) {for (int j = 1; j <= n; ++j) {if (s.charAt(i - 1) == t.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1;else dp[i][j] = dp[i][j - 1];}}return dp[m][n] == m ? true : false;}
}

 

原题链接： 115 不同的子序列

 

本题较难。按dp五部曲分析如下：

1. 确定dp数组及下标的含义：以s[i - 1]结尾的s子序列中出现的以t[j - 1]为结尾的t的子序列的个数；
2. 确定状态转移方程：s[i - 1] == t[j - 1]时，dp[i][j]由两种情况的和而来：即dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]，s[i - 1] != t[j - 1]时，dp[i][j]则只有一种转移情况：dp[i][j] = dp[i - 1][j]；
3. dp数组的初始化：对于dp[i][0]，由于t的空串为任意字符串的子序列，因此dp[i][0]= 1。同时，对于dp[0][j](0 < j < n)，由于s的空串除空串外不可能有任何子序列，因此dp[0][j] = 0；
4. 确定遍历顺序：从上面方程的推导过程来看，一定是从上往下从左往右的；
5. 举例推导：略。

以下是代码：

class Solution {static final int MOD = (int) 1e9 + 7;public int numDistinct(String s, String t) {char[] cs  = s.toCharArray(), ct = t.toCharArray();int m = s.length(), n = t.length();int[][] dp = new int[m + 1][n + 1];for (int i = 0; i <= m; ++i) {dp[i][0] = 1;}for (int i = 1; i <= m; ++i) {for (int j = 1; j <= n; ++j) {if (cs[i - 1] == ct[j - 1]) dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % MOD;else dp[i][j] = dp[i - 1][j] % MOD;}}return dp[m][n] % MOD;}
}

这篇关于代码随想录算法训练营Day55|LC392 判断子序列LC115 不同的子序列LC583 两个字符串的删除操作的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---