看完想法：在dp遞推公式那里沒有太看得懂。首先dp【i】的狀態肯定是由前面的dp【0】到dp【i-1】推出的，但是dp【0】到dp【i-1】可以推出dp【i】有個前提就是(nums【i】 > nums【0到i-1任意一個】),例如nums【1】 = 2, nums【3】 = 5,那么可以推出dp【3】 = dp【1】 + 1,反之則不行。可是在nums【0】到nums【i-1】可能不止一個小于nums【i】的數而我們又要取從0到i-1最大的那個遞增子序列，所以只能從0到i-1都遍歷一遍然后取最大的一個也就是雙層循環，外面遍歷i里面遍歷0到i-1，所以就可以用j來表示0到i-1的數那么就可以得出遞推公式 if(nums【i】>nums【j】)dp【i】 = max(dp【i】, dp【j】 + 1);

int lengthOfLIS(vector<int>& nums) {//0，1單獨考慮if (nums.size() <= 1) return nums.size();//根據定義，可以只定義到nums.size()vector<int> dp(nums.size(), 1);//設置resizeint 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;

時間復雜度：O（n^2）

?674. 最長連續遞增序列

看完想法：最長遞增和最長連續遞增有很大的區別。最長連續遞增序列是 [1,3,5], 長度為3。盡管 [1,3,5,7] 也是升序的子序列, 但它不是連續的，因為 5 和 7 在原數組里被 4 隔開。在遞推公式中展現了這二者的區別，最長連續遞增只需要考慮dp[i] 和dp[i-1]，不需要考慮i-1之前的，所以只需要單層for循環

int findLengthOfLCIS(vector<int>& nums) {//0，1單獨考慮if (nums.size() <= 1) return nums.size();//根據定義，可以只定義到nums.size()vector<int> dp(nums.size(), 1);//設置resizeint result = 0;for (int i = 1; i < nums.size(); i++) {int j = i-1;if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);if (dp[i] > result) result = dp[i]; // 取長的子序列}return result;}

時間復雜度：O（n）

718. 最長重復子數組?

看完想法：注意題目中說的子數組，其實就是連續子序列。根據卡哥的想法，dp[i][j]數組的定義是下標為i-1的A和下標為j-1的B的最長重復子序列。如果定義下標為i也可以，就是會在數組初始化的時候比較麻煩,需要自己定義第一行和第一列?。遞推公式：dp[i][j]的狀態只能由dp[i - 1][j - 1]推導出來。即當A[i - 1] 和B[j - 1]相等的時候，dp[i][j] = dp[i - 1][j - 1] + 1;

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;