1143.最長公共子序列
動(dòng)規(guī)五部曲
確定dp數(shù)組（dp table）以及下標(biāo)的含義
dp[i][j]：長度為[0, i - 1]的字符串text1與長度為[0, j - 1]的字符串text2的最長公共子序列為dp[i][j]
確定遞推公式
text1[i - 1] == text2[j - 1]?dp[i][j] = dp[i - 1][j - 1] + 1;
text1[i - 1] ！= text2[j - 1]??dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
dp數(shù)組初始化
dp[i][0] = 0??dp[0][j]=0
確定遍歷順序
要從前向后笼吟，從上到下來遍歷這個(gè)矩陣库物。
舉例推導(dǎo)dp數(shù)組
intlongestCommonSubsequence(string text1,string text2){vector<vector<int>>dp(text1.size()+1,vector<int>(text2.size()+1,0));for(inti=1;i<=text1.size();i++){for(intj=1;j<=text2.size();j++){if(text1[i-1]==text2[j-1]){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}}returndp[text1.size()][text2.size()];}
1035.不相交的線?
直線不能相交，這就是說明在字符串A中 找到一個(gè)與字符串B相同的子序列贷帮，且這個(gè)子序列不能改變相對順序戚揭，只要相對順序不改變，鏈接相同數(shù)字的直線就不會(huì)相交撵枢。
同上題最長公共子序列
53.?最大子序和??動(dòng)態(tài)規(guī)劃?
動(dòng)規(guī)五部曲
確定dp數(shù)組（dp table）以及下標(biāo)的含義
dp[i]：包括下標(biāo)i（以nums[i]為結(jié)尾）的最大連續(xù)子序列和為dp[i]民晒。
確定遞推公式
dp[i] = max(dp[i - 1] + nums[i], nums[i]);
dp數(shù)組初始化
dp[0] = nums[0]
確定遍歷順序
遞推公式中dp[i]依賴于dp[i - 1]的狀態(tài)，需要從前向后遍歷
舉例推導(dǎo)dp數(shù)組
intmaxSubArray(vector<int>&nums){if(nums.size()==0)return0;vector<int>dp(nums.size());dp[0]=nums[0];intresult=dp[0];for(inti=1;i<nums.size();i++){dp[i]=max(dp[i-1]+nums[i],nums[i]);// 狀態(tài)轉(zhuǎn)移公式if(dp[i]>result)result=dp[i];// result 保存dp[i]的最大值}returnresult;}
