LeetCode 300.最長(zhǎng)遞增子序列

題目鏈接：力扣（LeetCode）官網(wǎng) - 全球極客摯愛(ài)的技術(shù)成長(zhǎng)平臺(tái)

題目描述：給你一個(gè)整數(shù)數(shù)組 nums ，找到其中最長(zhǎng)嚴(yán)格遞增子序列的長(zhǎng)度。

子序列 是由數(shù)組派生而來(lái)的序列，刪除（或不刪除）數(shù)組中的元素而不改變其余元素的順序。例如，[3,6,2,7] 是數(shù)組 [0,3,1,6,2,2,7] 的子序列。

解題思路

通過(guò)兩次循環(huán)，在j<i時(shí)判斷nums[j]是否小于nums[i]，如果是則子序列長(zhǎng)度加一

1. 確定dp數(shù)組（dp table）以及下標(biāo)的含義

dp[i]代表從0到i遞增子序列的長(zhǎng)度

1. 確定遞推公式

if(nums[i] > nums[j]) dp[i] = max(dp[i],dp[j]+1);

1. dp數(shù)組如何初始化

一個(gè)數(shù)就是長(zhǎng)度為1的子序列，所以全部初始化為1.

1. 確定遍歷順序

從遞歸公式其實(shí)已經(jīng)可以看出，一定是從前向后遍歷，因?yàn)閐p[i]，依靠dp[i - 1]的數(shù)值。

1. 舉例推導(dǎo)dp數(shù)組

class Solution {
public:int lengthOfLIS(vector<int>& nums) {if(nums.size() == 1) return 1;vector<int> dp(nums.size(),1);int result = 0;for(int i=1;i<nums.size();i++){for(int j=0;j<i;j++){if(nums[i] > nums[j]){dp[i] = max(dp[i],dp[j]+1);}result = max(result,dp[i]);}}return result;}
};

總結(jié)：

• 子序列要二重遍歷。

LeetCode 674.最長(zhǎng)連續(xù)遞增序列

題目鏈接：力扣（LeetCode）官網(wǎng) - 全球極客摯愛(ài)的技術(shù)成長(zhǎng)平臺(tái)

題目描述：給定一個(gè)未經(jīng)排序的整數(shù)數(shù)組，找到最長(zhǎng)且 連續(xù)遞增的子序列，并返回該序列的長(zhǎng)度。

連續(xù)遞增的子序列 可以由兩個(gè)下標(biāo) l 和 r（l < r）確定，如果對(duì)于每個(gè) l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是連續(xù)遞增子序列。

解題思路

1. 確定dp數(shù)組（dp table）以及下標(biāo)的含義

dp[i]代表到nums[i]為止，最長(zhǎng)的連續(xù)遞增子序列

1. 確定遞推公式

如果前一個(gè)前一個(gè)數(shù)小于后一個(gè)數(shù)，也就是遞增的，我們就將當(dāng)前dp+1，如果不小于，就不操作，也就是將其置1，初始化時(shí)已經(jīng)置1，所以不用操作。

if(nums[i] > nums[i-1]) dp[i] = dp[i-1]+1;

1. dp數(shù)組如何初始化

全部初始化為1

1. 確定遍歷順序

正序遍歷即可

1. 舉例推導(dǎo)dp數(shù)組

class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {vector<int> dp(nums.size(),1);int result = 1;for(int i=1;i<nums.size();i++){if(nums[i] > nums[i-1]){dp[i] = dp[i-1]+1;}result = max(result,dp[i]);}return result;}
};

總結(jié)：

• 較為簡(jiǎn)單

LeetCode 718.最長(zhǎng)重復(fù)子數(shù)組

題目鏈接：力扣（LeetCode）官網(wǎng) - 全球極客摯愛(ài)的技術(shù)成長(zhǎng)平臺(tái)

題目描述：給兩個(gè)整數(shù)數(shù)組 nums1 和 nums2 ，返回 兩個(gè)數(shù)組中 公共的 、長(zhǎng)度最長(zhǎng)的子數(shù)組的長(zhǎng)度 。

解題思路

1. 確定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é)尾的字符串 ）

1. 確定遞推公式

即當(dāng)A[i - 1] 和B[j - 1]相等的時(shí)候，dp[i][j] = dp[i - 1][j - 1] + 1;

不相等就是0了，也就不用操作

1. dp數(shù)組如何初始化

全部初始化為0

1. 確定遍歷順序

先遍歷數(shù)組1，或者數(shù)組2都可以。

1. 舉例推導(dǎo)dp數(shù)組

class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,0));int result = 0;for(int i=1;i<=nums1.size();i++){for(int j=1;j<=nums2.size();j++){if(nums1[i-1] == nums2[j-1]){dp[i][j] = dp[i-1][j-1]+1;}result = max(result,dp[i][j]);}}return result;}
};

總結(jié)：

• 本來(lái)以為是要搞幾個(gè)狀態(tài)，沒(méi)想到直接用二維來(lái)代表倆數(shù)組遍歷的情況了。

?