392.判断子序列
动态规划五部曲
确定dp数组（dp table）以及下标的含义
dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。
确定递推公式
if (s[i - 1] == t[j - 1])，那么dp[i][j] = dp[i - 1][j - 1] + 1;
if (s[i - 1] != t[j - 1]) dp[i][j] = dp[i][j - 1];
dp数组初始化
dp[i][0] =0 dp[0][j]=0
确定遍历顺序
dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]，遍历顺序从上到下，从左到右
举例推导dp数组
boolisSubsequence(string s,string t){vector<vector<int>>dp(s.size()+1,vector<int>(t.size()+1,0));for(inti=1;i<=s.size();i++){for(intj=1;j<=t.size();j++){if(s[i-1]==t[j-1])dp[i][j]=dp[i-1][j-1]+1;elsedp[i][j]=dp[i][j-1];}}if(dp[s.size()][t.size()]==s.size())returntrue;returnfalse;}
115.不同的子序列
动规五部曲
确定dp数组（dp table）以及下标的含义
dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]
确定递推公式
s[i - 1] == t[j - 1] dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
s[i - 1] != t[j - 1] dp[i][j] = dp[i - 1][j]
dp数组初始化
dp[i][0]=1 dp[0][j]=0
确定遍历顺序
从递推公式dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; 和 dp[i][j] = dp[i - 1][j]; 中可以看出dp[i][j]都是根据左上方和正上方推出来的
for(inti=1;i<=s.size();i++){for(intj=1;j<=t.size();j++){if(s[i-1]==t[j-1]){dp[i][j]=dp[i-1][j-1]+dp[i-1][j];}else{dp[i][j]=dp[i-1][j];}}}
举例推导dp数组
