代码随想录打卡第52天|300.最长递增子序列；674. 最长连续递增序列；718. 最长重复子数组

300.最长递增子序列

关键点1：dp数组的含义

对nums[]中的元素j的最长严格递增子序列的长度是dp[j]；

关键点2：递归公式的推导

每个j都可以推出一个dp[i],所以求dp[i]与dp[j]+1的最大值：dp[i] = Math.max(dp[j]+1,dp[i]);          

关键点3：dp数组初始化

每个dp元素都至少为1： Arrays.fill(dp,1);

关键点4：遍历顺序

由于下一个dp值与上一个dp值有关，因此for循环从前往后遍历（从0开始遍历是为了维护dp数组的完整性，找出dp数组的中元素的最大值）。

class Solution {public int lengthOfLIS(int[] nums) {// 对nums[]中的元素j的最长严格递增子序列的长度是dp[j]int[] dp = new int[nums.length];// 初始化，每个dp元素都至少为1Arrays.fill(dp,1);int result = 0;for(int i = 0;i < nums.length;i++){for(int j = 0;j < i;j++){if(nums[i]>nums[j]){//每个j都可以推出一个dp[i],所以求dp[i]与dp[j]+1的最大值dp[i] = Math.max(dp[j]+1,dp[i]);              }                                }// 最终的结果不是dp[nums.length-1],因为最长严格递增子序列不一定包含最后那个值//而是对整个dp数组中的元素求最大值，因此可在这个地方进行最终结果的保存更新result = Math.max(result,dp[i]); }      return result;}
}

674. 最长连续递增序列

关键点1：dp数组的含义

对nums[]中的元素j的最长严格递增子序列的长度是dp[j]；

关键点2：递归公式的推导

因为必须是连续的，所以只用比较前后两个元素就可以了，不用像上一题写一个for j的循环，遍历小于i的每个元素 nums[j]与nums[i]的关系：dp[i] = dp[i - 1]+1;      

关键点3：dp数组初始化

每个dp元素都至少为1： Arrays.fill(dp,1);

关键点4：遍历顺序

由于下一个dp值与上一个dp值有关，因此for循环从前往后遍历（0已经初始化，且为使递归公式的dp[i-1]有意义，i从1开始遍历）。

class Solution {public int findLengthOfLCIS(int[] nums) {// 最长且 连续递增的子序列int[] dp = new int[nums.length];// 初始化，每个dp元素都至少为1Arrays.fill(dp,1);int result = 0;for(int i = 1; i < nums.length;i++){//因为必须是连续的，所以只用比较前后两个元素就可以了//不用像上一题写一个for j的循环，遍历小于i的每个元素 nums[j]与nums[i]的关系if(nums[i] > nums[i-1]){dp[i] = dp[i-1]+1;}}// 最终的结果不是dp[nums.length-1],而是对整个dp数组中的元素求最大值,因为最长连续递增子序列不一定包含最后那个值for(int i = 0;i < dp.length;i++){result = Math.max(result,dp[i]);}return result;}
}

718. 最长重复子数组 

关键点1：dp数组的含义

dp[i][j]是以i-1,j-1为结尾的公共最长子数组的长度；

关键点2：递归公式的推导

 if(nums1[i-1] == nums2[j-1])，则i和j同时移动，所以为i-1,j-1；dp[i][j] = dp[i-1][j-1]+1;

关键点3：dp数组初始化

每个dp[i][j]元素都初始化为0，因为dp[0][j] =dp[-1][j-1]+1; ,dp[i][0] = dp[i-1][-1]+1;都出现了无意义的dp[-1]，所以dp[0][j] 和 dp[i][0] 都初始化为0 ，而其它元素也可初始化为0，所以整个数组初始化为0；

关键点4：遍历顺序

由于下一个dp值与上一个dp值有关，因此for循环从前往后遍历（0已经初始化，且为使递归公式的dp[i-1][j-1]有意义，i,j都从1开始遍历）。

class Solution {public int findLength(int[] nums1, int[] nums2) {// dp[i][j]是以i-1,j-1为结尾的公共最长子数组的长度int[][] dp = new int[nums1.length+1][nums2.length+1];int result = 0;for(int i = 1;i <=nums1.length;i++){for(int j = 1;j <= nums2.length;j++){if(nums1[i-1] == nums2[j-1]){dp[i][j] = dp[i-1][j-1]+1;result = Math.max(dp[i][j],result);}}            }return result;}
}