代碼隨想錄算法訓練營|第五十四天|300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组。刷题心得（c++）

本文主要是介绍代碼隨想錄算法訓練營|第五十四天|300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组。刷题心得（c++），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

讀題

300.最长递增子序列

看完代码随想录之后的想法

思想上很簡單，dp[i]表示i之前的包括i的numbers[i]節尾的最長上升子序列的長度

並且透過兩層迴圈，一層遍歷全部，一層遍歷到i，透過比較當前dp[i]還是dp[j] + 1哪個比較大，來更新動態規劃的dp數組數據。

674. 最长连续递增序列

自己看到题目的第一想法

稍微將300轉一下就好，dp[i] 改為到i之前的最長連續子序列長度為dp[i]，公式轉為假設nums[i] > nums[i - 1] 就將dp[i] 的值改為前一個值的個數 + 1就好了

718. 最长重复子数组

自己看到题目的第一想法

的確比較有難度，要思考如何去找出重複子序列，但是將nums1以及nums2的對應表畫出來後，會發現可以透過左上角的值來看重複度，假設左上角為1，那就代表前一個num2的值與前一個num1的值相等，所以當前的值如果也相等，那就要基於dp[i - 1][j - 1]的值 + 1，雖然這個想法完整了，但是自己對於下標的定義沒有想的很清楚，主要是透過畫圖模擬，找出規律並推出遞推公式。

看完代码随想录之后的想法

看完之後，發現卡哥的做法比較直覺一點，但要想到比較難，我的想法主要是透過畫圖推出，而卡哥是直接在整體数組框架上往外擴一層，就免除了我在nums1[i] != nums2[j] 需要做的額外操作，兩者都可以通過，只是方法不同而已，下標的定義也讓我之前比較模糊的定義有了清晰的了解。

300.最长递增子序列 - 實作

思路

定義DP數組以及下標的含意

dp[i] 代表 i 之前包含i 的number[i] 結尾的最大遞增子序列的長度是多少
遞推公式

透過兩層迴圈，一個遍歷numbers.size的數組的長度，一個遍歷到i的長度

if (number[i] > number[j]) dp[i] = max(dp[i], dp[j] + 1)
根據遞推公式、題意以及定義，確定DP數組如何初始化

每個數做為結尾都至少含有一個，所以將數組初始化為1
確定遍歷順序

0 到 i 因為需要前面的數據來進行遍歷，所以是由前往後。

0 到 i - 1 只要都有遍歷到就可以了，往前或往後都沒有關係，但為了方便理解，默認由前往後

Code

class Solution {
public:int lengthOfLIS(vector<int>& nums) {vector<int> dp (nums.size(), 1);int result = 1;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. 最长连续递增序列 - 實作

思路

定義DP數組以及下標的含意

dp[i] 代表 i 之前包含i 的number[i] 結尾的最長連續遞增子序列的長度是多少
遞推公式

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

假設number[i] > number[i - 1] 代表number[i - 1]之前都是連續遞增的，所以加上當前的數

如果沒有大於，就維持初始化
根據遞推公式、題意以及定義，確定DP數組如何初始化

每個數做為結尾都至少含有一個，所以將數組初始化為1
確定遍歷順序

0 到 i 因為需要前面的數據來進行遍歷，所以是由前往後。

Code

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

718. 最长重复子数组 - 實作

思路

定義DP數組以及下標的含意

dp[i][j] 代表 0~ i 的nums1以及 0 ~ j 的nums2最長連續遞增子序列長度為dp[i][j]
遞推公式

if(nums1[i] == nums2[j]) { if(i > 0 && j > 0) dp[i][j] = dp[i - 1][j - 1] + 1; else dp[i][j] += 1; }

假設nums1[i] == nums[j] 其中一個不大於 0 則只加一，如果都大於1 則看左上角的數
根據遞推公式、題意以及定義，確定DP數組如何初始化

最少為0，所以初始化為0
確定遍歷順序

因為需要左上角的數據來進行遍歷，所以是由前往後。

Code

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