您现在的位置是：首页 >技术教程 >代码随想录第五十二天|最长子序列网站首页技术教程

Leetcode 300. 最长递增子序列

题目链接: 最长递增子序列
自己的思路:想不到！！！！！

正确思路:这道题感觉也很简单，但是就是想不到！！！！！！直接动规五部曲：1、dp数组的含义：dp[i]表示以nums[i]结尾的最长递增子序列的长度；2、递推公式：当当前的数nums[i]大于前面某一个数nums[j]的时候，那么dp[i]就会等于dp[j]+1，那么我们一定会遍历i之前所有的j来得到最大的那个dp[i]，这样的话，我们就要找其中最大的那个dp[i]，所以dp[i]=max(dp[j]+1,dp[i])；3、dp数组的初始化：由于我们递增子序列的长度最小为1，所以我们将所有的数都初始化为1即可；4、遍历顺序：由于是由前面的元素得到后面的元素，所以是从前向后遍历；5、打印dp数组：主要用于debug！！！！这里需要注意的是，因为我们要找最长的子序列，所以我们应该使用一个临时变量记录一下dp[i]中的最大值！！！！

代码:

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int result = 1;
        Arrays.fill(dp,1);
        for (int i =1;i<nums.length;i++){
            for (int j=0;j<=i;j++){
                //递推公式
                if (nums[i]>nums[j]){
                    dp[i] = Math.max(dp[j]+1,dp[i]);
                }
                //记录其中的最大值
                result = Math.max(result,dp[i]);
            }
        }
        return result;
    }
}

Leetcode 674. 最长连续递增序列

题目链接: 最长连续递增序列
自己的思路:感觉比上一个题简单一些吧，因为这里我们只需要比较当前的元素和前一个元素即可，根据条件来更新dp数组即可，具体细节参考上一个题！！！！！！

正确思路:

代码:

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int[] dp = new int[nums.length];
        int result = 1;
        Arrays.fill(dp,1);
        for (int i =1;i<nums.length;i++){
            //只和前一个元素进行比较
            if (nums[i]>nums[i-1]){
                dp[i] = dp[i-1] + 1; 
            }
            result = Math.max(dp[i],result);
        }
        return result;
    }
}

Leetcode 718. 最长重复子数组

题目链接: 最长重复子数组
自己的思路:思路差不多，没调出来！！！

正确思路:这道题最重要的问题是dp数组的定义，使用二维dp数组来表示状态转移方程；动规五部曲：1、dp数组的含义：dp[i][j]表示以nums[i-1]和nums[j-1]为结尾的最长重复数组的长度，这里为什么要定义i-1和j-1呢，如果我们假设定义的是以nums[i]和nums[j]为结尾的最长重复数组的长度的话，那么我们在dp数组初始化的时候，dp[i][0]和dp[0][i]需要遍历两个数组才可以得到值，相当于dp数组的第一行和第一列，这样就会麻烦很多，所以我们这样来定义dp数组；2、递推公式：当nums[i-1]==nums[j-1]的时候，我们要进行dp数组的更新，因为在原来dp[i-1][j-1]的基础上加1即可，为什么是i-1和j-1，因为两个数组的索引是同时在移动的；3、dp数组初始化，这里我们初始化dp[0][j]和dp[i][0]的时候不需要思考很多，只要初始化为0即可，因为这两个都是没有意义的，后面的其他数由于都会被前面覆盖，所以我们初始化为0；4、遍历顺序：由于后面的数都是由前面的数得到的，所以我们从前向后遍历；5、打印dp数组：主要用于debug！！！！！

代码:

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int result = 0;
        int[][] dp = new int[m+1][n+1];

        for (int i =1;i<=m;i++){
            for (int j=1;j<=n;j++){
                //递推公式
                if (nums1[i-1]==nums2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    result = Math.max(result,dp[i][j]);
                }
            }
        }
        return result;
        
    }
}