动态规划---最长序列问题详解

代码随想录day 52 动态规划模块序列问题

1.leetcode 300. 最长递增子序列

1.1 思路及解题步骤

  这题找最长的子序列问题，用动态规划的方法解题，那么就直接用动态规划的做题步骤来分析。

  按照动态规划的做题步骤来分析

   1.确定dp数组以及下标的含义

dp[i]表示i之前包括i的以nums[i]结尾最长上升子序列的长度

   2. 确定递推公式

dp[i]由前一个dp[j]推导出来，j不是i-1,jdp[j]) dp[i]=Math.max(dp[i],dp[j]+1)

  3. dp数组的初始化问题

把dp数组中所有的值初始化为1

  4.确定遍历顺序

从前往后的遍历两层

  5.推导dp数组

1.2 详细代码分析

> class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp=new int[nums.length];
        int count=1;//初始最大的序列长度
        for(int i=0;i<nums.length;i++){
            dp[i]=1;//对所有dp数组进行初始化
            for(int j=0;j<i;j++){
                if(nums[j]<nums[i]){
                    dp[i]=Math.max(dp[j]+1,dp[i]);
                }
            }
            
            count=Math.max(count,dp[i]);
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

2.leetcode 674. 最长连续递增序列

2.1 思路及解题步骤

  这题跟上题思路类似，但是这题求的是连续的序列长度，所以就考虑nums[i]>nums[i-1]
  按照动态规划的做题步骤来分析

   1.确定dp数组以及下标的含义

dp[i]表示i之前包括i的以nums[i]结尾最长上升子序列的长度

   2. 确定递推公式

递推公式 dp[i+1]=dp[i]+1

  3. dp数组的初始化问题

把dp数组中所有的值初始化为1

  4.确定遍历顺序

从前往后的遍历两层

  5.推导dp数组

2.2 详细代码分析

class Solution {
    public int findLengthOfLCIS(int[] nums) {
      int[] dp=new int[nums.length];  
      for(int i=0;i<nums.length;i++){
             dp[i]=1;//初始化所有dp数组的值
         }
         int count=1;
      for(int i=0;i<nums.length-1;i++){
              if(nums[i+1]>nums[i]){
                  dp[i+1]=dp[i]+1;
          }
          count=Math.max(dp[i+1],count);
      }
      return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---

3.leetcode 718. 最长重复子数组

3.1 思路及解题步骤

  这题比较两个数组就得用dp二维数组来做了

  按照动态规划的做题步骤来分析

   1.确定dp数组以及下标的含义

dp[i][j]表示以nums1[i-1]和nums[j-1]结尾时候的最长公共数组

   2. 确定递推公式

dp[i][j]=dp[i-1][j-1]+1

  3. dp数组的初始化问题

把dp数组中所有的值初始化为0

  4.确定遍历顺序

从前往后的遍历两层

3.2 详细代码分析

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
     int[][] dp = new int[nums1.length+1][nums2.length+1];
     //dp[0][0]=0;
     int count=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;
            count=Math.max(dp[i][j],count);
             }

         }
        
     }
     return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18