【随想录】Day54—第九章动态规划part15

本文主要是介绍【随想录】Day54—第九章动态规划part15，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目1: 判断子序列

题目链接：392. 判断子序列

1- 思路

动规五部曲

1. 确定 dp 数组含义
- dp[i][j] 以 i-1 为结尾的字符串 s 和，以 j-1 为结尾的字符串 t 相同子序列的长度
2. 确定递推公式
- 2.1 相遇两个字符相同的情况：dp[i][j] = dp[i-1][j-1]+1;
- 2.2 不同的情况 dp[i][j] = dp[i][j-1];
3. dp 数组初始化
- 初始化都为 0
4. 遍历顺序
- i 从 1 开始遍历到 i <= s.length()
- j 从 1 开始遍历到 i <= t.length()
5. 推导dp 数组
- 返回

return dp[s.length()][t.length()]==s.length()

2- 题解

⭐ 判断子序列——题解思路

在这里插入图片描述

class Solution {public boolean isSubsequence(String s, String t) {// 1. 定义 dp 数组// 代表 dp[i][j] 代表 长为j的 t 是不是 s 的子序列int[][] dp = new int[s.length()+1][t.length()+1];// 2. 确定递推公式// if(s.charAt(i) == t.charAt(j) )dp[i][j] = dp[i-1][j-1];// 3. 初始化// 第一列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]+1;}else{dp[i][j] = dp[i][j-1];}}}return dp[s.length()][t.length()]==s.length();}
}

题目2: 不同的子序列

题目链接：115. 不同的子序列

1- 思路

动规五部曲

1. 确定 dp 数组含义
- dp[i][j] 代表以 i - 1 结尾的 s 中有以 j - 1 为结尾的 t 的个数
2. 确定递推公式
- 2.1 遇到字符相等： s：baggg、t：bag
  - 此时 s 和 t 的最后一位相等，此时子序列 t 的组成有两种情况：
  - ① 前面的 ba ([i-1][j-1]) 出现次数和当前相等的 g 组成 bag，意义就是bagg中有多少个ba
  - ② 前面的 bag ([i-1][j])出现的次数，意义就是bagg中有多少个bag
- 2.2 遇到字符不相等
  - 此时只需要考虑 bagg中有多少个bag
3. dp 数组初始化
- 第一行，s 怎么删除元素可以变为 t
- dp[i][0] 需要初始化为 1有一种方法就是将 s 中的所有字符都删了这一种方法因此 dp[i][0] 需要初始化为 1
- 第一列，dp[0][i] 此时 s 为 0 ，s 怎么删除元素可以变为 t ，不能变为 t 所以默认为 0
4. 遍历顺序
- i 从 1 遍历到 i<=s.length()
- j 从 1 遍历到 j<=j.length()
5. 推导dp 数组

疑问

在递推公式的考虑过程中，为什么 s[i-1]==t[j-1] 时候不需要考虑当前字母 s[i-1] 和 t[j-1]

理解

这个 dp[i][j] 含义：为了好理解

我们换一下定义：以i为结尾的s子序列中出现以j结尾的t子序列个数。
递推公式还是不变：dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
s: baggg 、 t:bag。此时 i 与 j 都指向最后的元素。
dp[i-1][j-1] 当最后一个元素相等时：意义就是bagg中有多少个ba
dp[i-1][j] 当最后一个元素相等时，意义就是bagg中有多少个bag

1与2是两种不同的情况相加

2- 题解

⭐不同的子序列——题解思路

在这里插入图片描述

class Solution {public int numDistinct(String s, String t) {// 1. 定义 dp数组int[][] dp = new int[s.length()+1][t.length()+1];// 2. 递推公式// if(s.charAt(i)==t.charAt(j))// {dp[i][j] = dp[i-1][j-1] + dp[i-1][j];}// else{dp[i][j] = dp[i-1][j]}// 3. 初始化for (int i = 0; i < s.length() + 1; i++) {dp[i][0] = 1;}// 4. 遍历顺序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()];}
}