300.最長(zhǎng)遞增子序列?
動(dòng)規(guī)五部曲
dp[i]的定義
dp[i]表示i之前包括i的以nums[i]結(jié)尾的最長(zhǎng)遞增子序列的長(zhǎng)度
狀態(tài)轉(zhuǎn)移方程
位置i的最長(zhǎng)升序子序列等于j從0到i-1各個(gè)位置的最長(zhǎng)升序子序列 + 1 的最大值。
dp[i] = max(dp[i], dp[j] + 1);
dp[i]的初始化
每一個(gè)i票彪，對(duì)應(yīng)的dp[i]（即最長(zhǎng)遞增子序列）起始大小至少都是1.
確定遍歷順序
dp[i] 是有0到i-1各個(gè)位置的最長(zhǎng)遞增子序列 推導(dǎo)而來(lái)降铸，那么遍歷i一定是從前向后遍歷
for(inti=1;i<nums.size();i++){for(intj=0;j<i;j++){if(nums[i]>nums[j])dp[i]=max(dp[i],dp[j]+1);}if(dp[i]>result)result=dp[i];// 取長(zhǎng)的子序列}
674.?最長(zhǎng)連續(xù)遞增序列?
動(dòng)規(guī)五部曲
確定dp數(shù)組（dp table）以及下標(biāo)的含義
dp[i]：以下標(biāo)i為結(jié)尾的連續(xù)遞增的子序列長(zhǎng)度為dp[i]
確定遞推公式
如果 nums[i] > nums[i - 1]，那么以 i 為結(jié)尾的連續(xù)遞增的子序列長(zhǎng)度 一定等于 以i - 1為結(jié)尾的連續(xù)遞增的子序列長(zhǎng)度 + 1 桶蝎。
即：dp[i] = dp[i - 1] + 1;
dp數(shù)組初始化
p[i]初始為1
確定遍歷順序
dp[i + 1]依賴dp[i]谅畅，從前向后遍歷
intfindLengthOfLCIS(vector<int>&nums){if(nums.size()==0)return0;intresult=1;vector<int>dp(nums.size(),1);for(inti=1;i<nums.size();i++){if(nums[i]>nums[i-1]){// 連續(xù)記錄dp[i]=dp[i-1]+1;}if(dp[i]>result)result=dp[i];}returnresult;}
18.?最長(zhǎng)重復(fù)子數(shù)組??
動(dòng)規(guī)五部曲
確定dp數(shù)組（dp table）以及下標(biāo)的含義
dp[i][j] ：以下標(biāo)i - 1為結(jié)尾的A，和以下標(biāo)j - 1為結(jié)尾的B胜茧，最長(zhǎng)重復(fù)子數(shù)組長(zhǎng)度為dp[i][j]仇味。 （特別注意： “以下標(biāo)i - 1為結(jié)尾的A” 標(biāo)明一定是 以A[i-1]為結(jié)尾的字符串 ） i j 從 1開(kāi)始
確定遞推公式
dp[i][j] = dp[i - 1][j - 1] + 1;
dp數(shù)組初始化
dp[i][0] 和dp[0][j]初始化為0
確定遍歷順序
外層for循環(huán)遍歷A，內(nèi)層for循環(huán)遍歷B
for(inti=1;i<=nums1.size();i++){for(intj=1;j<=nums2.size();j++){if(nums1[i-1]==nums2[j-1]){dp[i][j]=dp[i-1][j-1]+1;}if(dp[i][j]>result)result=dp[i][j];}}
舉例推導(dǎo)dp數(shù)組
