*300. 最長遞增子序列

leetcode題目地址

dp數組含義：
dp[i]表示以nums[i]結尾的最長遞增子序列長度，即以nums[i]結尾的子序列的長度。
j從0向i遍歷，遇到num[i] > num[j], dp[i] = max(dp[j]+1, dp[i]);

時間復雜度： $O(n^2)$
空間復雜度： $O(n)$

// java
class Solution {public int lengthOfLIS(int[] nums) {int len = nums.length; int[] dp = new int[len];int result = 1;// for(int i=0; i<len; i++) dp[i] = 1;Arrays.fill(dp, 1);for(int i=1; i<len; i++){for(int j=0; j<i; j++){if(nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j]+1);}if(result < dp[i]) result = dp[i];}return result;}
}

674. 最長連續遞增序列

leetcode題目地址

基礎解法（非動規）

求最長連續遞增子序列，統計子序列記錄最長即可。在遞增中斷時，計數器要置為1而非0，因為下一個子序列從當前元素開始。

時間復雜度： $O(n)$
空間復雜度： $O(n)$

// java
class Solution {public int findLengthOfLCIS(int[] nums) {int result = 1;int cnt = 1;int len = nums.length;for(int i=1; i<len; i++){if(nums[i]>nums[i-1]) {cnt++;if(cnt > result) result = cnt;}else cnt = 1; // 計數器置為1}return result;}
}

動態規劃

dp數組含義：
dp[i]表示以nums[i]結尾的最長連續遞增子序列的長度。

初始化：
每個元素本身就是一個連續遞增子序列，因此初始化為1，即dp數組均初始化為1。

// java
class Solution {public int findLengthOfLCIS(int[] nums) {int len = nums.length;int[] dp = new int[len];Arrays.fill(dp, 1);int result = 1;for(int i=1; i<len; i++){if(nums[i] > nums[i-1]) dp[i] = dp[i-1]+1;result = Math.max(result, dp[i]);}return result;}
}

718. 最長重復子數組

leetcode題目地址

dp數組含義：
dp[i][j]表示 以nums1[i-1]結尾的子數組A 和以 以nums2[j-1]結尾的子數組B 的最長重復子數組長度。

這里為什么要用i-1和j-1？
因為dp[i][j]的更新依賴于dp[i-1][j-1]的值。也就是說，在nums1[i-1]和nums2[j-1]相等時，更新對應位置長度需要依賴nums1[i-2]和nums2[j-2]的最長重復子數組長度。
以題目示例1舉例：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]

• 當nums1[2] == nums2[0]時，當前位置的最長重復子數組長度依賴于前面的匹配情況，前面相等的串長度為0，因此這里dp[3][1]是1。
• 當nums1[3] == nums2[1]時，邏輯同上，dp[4][2]的更新依賴于前面的匹配情況，前面有一個元素匹配到，因此這里dp[4][2] = dp[3][1]+1 = 2
• 當nums1[4] == nums2[2]時，邏輯同上，dp[5][3]的更新依賴于前面的匹配情況，前面有兩個元素匹配到，因此這里dp[5][3] = dp[4][2]+1 = 3

到這里就可以總結出狀態轉移方程，dp[i][j] = dp[i-1][j-1] + 1
由于這里使用了i-1和j-1，在i和j為0時會越界。 因此整體將dp數組下標后移一位，來解決這一問題。（也可單獨處理i和j為0的情況，較復雜）

時間復雜度： $O(n^2)$
空間復雜度： $O(n)$

// java
class Solution {public int findLength(int[] nums1, int[] nums2) {int len1 = nums1.length;int len2 = nums2.length;int[][] dp = new int[len1+1][len2+1];int result  = 0;if(nums1[0] == nums2[0]) dp[1][1] = 1;for (int i=1; i<=len1; i++){for(int j=1; j<=len2; j++){if(nums1[i-1] == nums2[j-1]){dp[i][j] = dp[i-1][j-1]+1;}result = Math.max(result, dp[i][j]);// System.out.print(dp[i][j] + " ");}// System.out.println();}return result;}
}

滾動數組

注意：
1、思路同上，只是每一層的狀態是從上一層拷貝下來的，因此在遍歷nums2時要從后向前，防止將前面元素在上一層的狀態覆蓋
2、當遇到元素不相同是要將對應位置賦值0.

// java
class Solution {public int findLength(int[] nums1, int[] nums2) {int len1 = nums1.length;int len2 = nums2.length;int[] dp = new int[len2+1];int result  = 0;for (int i=1; i<=len1; i++){for(int j=len2; j>=1; j--){if(nums1[i-1] == nums2[j-1]){dp[j] = dp[j-1]+1;} else dp[j] = 0; // 注意這里不相等的時候要有賦0的操作result = Math.max(result, dp[j]);}}return result;}
}