392.判斷子序列?
動態(tài)規(guī)劃五部曲
確定dp數(shù)組（dp table）以及下標(biāo)的含義
dp[i][j] 表示以下標(biāo)i-1為結(jié)尾的字符串s，和以下標(biāo)j-1為結(jié)尾的字符串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數(shù)組初始化
dp[i][0] =0?dp[0][j]=0
確定遍歷順序
dp[i][j]都是依賴于dp[i - 1][j - 1] 和 dp[i][j - 1]蔚约，遍歷順序從上到下涂籽，從左到右
舉例推導(dǎo)dp數(shù)組
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.不同的子序列??
動規(guī)五部曲
確定dp數(shù)組（dp table）以及下標(biāo)的含義
dp[i][j]：以i-1為結(jié)尾的s子序列中出現(xiàn)以j-1為結(jié)尾的t的個數(shù)為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數(shù)組初始化
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]都是根據(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];}}}
舉例推導(dǎo)dp數(shù)組
