300. 最長遞增子序列

1.dp定義：dp[i]表示i之前包括i的以nums[i]結(jié)尾的最長遞增子序列的長度

2.遞推公式：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

注意這里不是要dp[i] 與 dp[j] + 1進(jìn)行比較，而是我們要取dp[j] + 1的最大值。

?3.初始化：每一個(gè)i，對應(yīng)的dp[i]（即最長遞增子序列）起始大小至少都是1.

class Solution {
public:int lengthOfLIS(vector<int>& nums) {if (nums.size() <= 1) return nums.size();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);}if (dp[i] > result) result = dp[i]; // 取長的子序列}return result;}
};

674. 最長連續(xù)遞增序列

1.dp定義：dp[i]：以下標(biāo)i為結(jié)尾的連續(xù)遞增的子序列長度為dp[i]。

2.遞推公式：如果 nums[i] > nums[i - 1]，那么以 i 為結(jié)尾的連續(xù)遞增的子序列長度 一定等于 以i - 1為結(jié)尾的連續(xù)遞增的子序列長度 + 1 。

即：dp[i] = dp[i - 1] + 1;

因?yàn)楸绢}要求連續(xù)遞增子序列，所以就只要比較nums[i]與nums[i - 1]，而不用去比較nums[j]與nums[i] （j是在0到i之間遍歷）。

?3.dp[i]應(yīng)該初始1;????????

class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {if (nums.size() == 0) return 0;int result = 1;vector<int> dp(nums.size() ,1);for (int i = 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];}return result;}
};

718. 最長重復(fù)子數(shù)組

1.dp定義：以下標(biāo)i - 1為結(jié)尾的A，和以下標(biāo)j - 1為結(jié)尾的B，最長重復(fù)子數(shù)組長度為dp[i][j]。

2.遞推公式：當(dāng)A[i - 1] 和B[j - 1]相等的時(shí)候，dp[i][j] = dp[i - 1][j - 1] + 1;

根據(jù)遞推公式可以看出，遍歷i 和 j 要從1開始！

3.初始化：根據(jù)dp[i][j]的定義，dp[i][0] 和dp[0][j]其實(shí)都是沒有意義的！

但dp[i][0] 和dp[0][j]要初始值，因?yàn)?為了方便遞歸公式dp[i][j] = dp[i - 1][j - 1] + 1;

所以dp[i][0] 和dp[0][j]初始化為0。

舉個(gè)例子A[0]如果和B[0]相同的話，dp[1][1] = dp[0][0] + 1，只有dp[0][0]初始為0，正好符合遞推公式逐步累加起來。

注：如果dp數(shù)組以i，j為結(jié)尾，那么初始化時(shí)，應(yīng)該為dp[i] = dp[j]時(shí)初始化為1

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;}if (dp[i][j] > result) result = dp[i][j];}}return result;}
};