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ù)組