目录
LeetCode 392.判断子序列
动态规划五步曲：
1.确定dp[i][j]的含义
2.找出递推公式
3.初始化dp数组
4.确定遍历顺序
5.打印dp数组
LeetCode 115.不同的子序列
动态规划五步曲：
1.确定dp[i][j]的含义
2.找出递推公式
3.初始化dp数组
4.确定遍历顺序
5.打印dp数组
LeetCode 392.判断子序列
文章讲解：代码随想录
视频讲解：动态规划，用相似思路解决复杂问题 | LeetCode：392.判断子序列_哔哩哔哩_bilibili
力扣题目：LeetCode 392.判断子序列
动态规划五步曲：
1.确定dp[i][j]的含义
dp[i][j]：在i对应的字符s和在j对应的字符t所得出最大公共子序列长度为dp[i][j]
2.找出递推公式
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];
}3.初始化dp数组
dp[i][0] = 0;
dp[0][j] = 0;
4.确定遍历顺序
从左往右，从上往下遍历
5.打印dp数组
代码如下（Java）：
class Solution {public boolean isSubsequence(String s, String t) {int length1 = s.length();int length2 = t.length();int[][] dp = new int[length1+1][length2+1];for(int i = 1; i <= length1; i++){for(int j = 1; j <= length2; 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];}}}if(dp[length1][length2] == length1){return true;}else{return false;}}
}LeetCode 115.不同的子序列
文章讲解：代码随想录
视频讲解：动态规划之子序列，为了编辑距离做铺垫 | LeetCode：115.不同的子序列_哔哩哔哩_bilibili
力扣题目：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
动态规划五步曲：
1.确定dp[i][j]的含义
dp[i][j]:包含下标i在内的字符和包含下标j在内的字符所得到的子序列的个数为dp[i][j]
2.找出递推公式
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];
}3.初始化dp数组
for(int i = 0; i < s.length()+1; i++) dp[i][0] = 1;4.确定遍历顺序
从左往右，从上往下遍历
5.打印dp数组
代码如下（Java）：
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()+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()];}
}
