代码随想录算法训练营第五十七天|392.判断子序列、115.不同

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数组