代码随想录算法训练营第五十二天 _ 动态规划_300. 最长递增子序列、674.最长连续递增序列、718.最长重复子数组。

学习目标：

动态规划五部曲：
① 确定dp[i]的含义
② 求递推公式
③ dp数组如何初始化
④ 确定遍历顺序
⑤ 打印递归数组 ---- 调试
引用自代码随想录！

60天训练营打卡计划！

学习内容：

300. 最长递增子序列

• 动态规划五步曲：
  ① 确定dp[i]的含义 ：以nums[i] 为尾的最长的递增子序列的长度
  ② 求递推公式 ： dp[i] = max(dp[j]+1, dp[i])
  ③ dp数组如何初始化 ： dp[i] = 1 (因为在判断后才会为dp赋值，有一些dp[i]保持为0，会导致整体都出问题)
  ④ 确定遍历顺序 ： i的遍历顺序是从小到大 j的遍历顺序随意（从小到大 / 从大到小）

class Solution {
    public int lengthOfLIS(int[] nums) {
        int size = nums.length;
        // 以nums[i]为结尾的递增子序列的最大长度。
        int[] dp = new int[size];
        int res = 1;

        // 初始化
        Arrays.fill(dp,1);

        for(int i = 1; i < size; i++){
            for(int j = 0; j < i; j++){
                if(nums[j] < nums[i])
                    dp[i] = Math.max(dp[j]+1,dp[i]);
            }
            System.out.print(dp[i] + " ");
            res = Math.max(res, dp[i]);
        }

        return res;
    }
}

674.最长连续递增序列

• 动态规划五步曲：
  ① 确定dp[i]的含义 ： 以nums[i] 为尾的最长的连续递增子序列的长度
  ② 求递推公式 ： dp[i] = dp[j-1]+1
  ③ dp数组如何初始化 ： dp[i] = 1
  ④ 确定遍历顺序 ： 从前向后

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int res = 1;
        int size = nums.length;
        int[] dp = new int[size];

        // 初始化
        Arrays.fill(dp,1);

        for(int i = 1; i < size; i++){
            // 因为是连续的，所以递推公式改变了。
            if(nums[i] > nums[i-1]){
                dp[i] = dp[i-1] + 1;
            }
            res = Math.max(res,dp[i]);
        }

        return res;
    }
}

718.最长重复子数组

因为本题中有两个数组，所以使用二维的dp数组会更符合我们的需求。

• 动态规划五步曲：
  ① 确定dp[i][j]的含义 ： 以 i-1 为结尾的 nums1 和以 j-1 为结尾的 nums2 的最大重复子数组的长度。
  ② 求递推公式 ： dp[i+1][j+1] = dp[i][j]+1;
  ③ dp数组如何初始化 ： 第一行和第一列为0
  ④ 确定遍历顺序 ： 从前向后
  二维数组的输出结果：
  
  按照上述的输出结果，本题应该可以压缩空间，使用一维数组实现！ – 还没学会，再学一学！

// 二维数组
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int size1 = nums1.length;
        int size2 = nums2.length;
        int res = 0;
        int[][] dp = new int[size1+1][size2+1];

        // 初始化   第一行和第一列为0

        for(int i = 0; i < size1; i++){
            for(int j = 0; j < size2; j++){
                if(nums1[i] == nums2[j])
                    dp[i+1][j+1] = dp[i][j]+1;
                // System.out.print(dp[i+1][j+1] + " ");
                res = Math.max(res, dp[i+1][j+1]);
            }
            // System.out.println("");
        }

        return res;
    }
}

学习时间：

• 上午两个半小时，整理文档半小时。