最长递增子序列

leecode题目链接

1. dp数组含义：以nums[i]结尾的最长递增子序列
2. 递推公式：dp[i]=max(dp[i],dp[j]+1)//若nums[j]<nums[i]
3. 初始化：每一个i，对应的dp[i]（即最长递增子序列）起始大小至少都是1.
4. 遍历顺序：从前向后遍历。后一个依赖前一个结果。

var lengthOfLIS = function(nums) {
    let dp=new Array(nums.length).fill(1)

    let result=1
    for(let i=1;i<nums.length;i++){
        for(let j=0;j<i;j++){
            if(nums[i]>nums[j]){
                dp[i]=Math.max(dp[i],dp[j]+1)
            }
        }

        result=Math.max(result,dp[i])
    }
    return result
};

最长连续递增序列

力扣题目链接(opens new window)
与上题区别：连续。
只需要与前一个元素比较。

1. dp数组含义：
   dp[i] 为以nums[i]结尾的最长连续递增序列
2. 递推公式：
   若dp[i-1]<dp[i]
   dp[i]=dp[i-1]+1，只需要与前一个元素比较，而不需要遍历i之前的元素。
3. 初始化：
   初始所有值=1，根据含义，以i结尾的序列，至少有一个元素
4. 遍历顺序
   顺序。

5. 打印dp数组

   
   
   image.png

var findLengthOfLCIS = function(nums) {
    let dp=new Array(nums.length).fill(1)
    let res=1
    for(let i=1;i<nums.length;i++){
        if(nums[i-1]<nums[i]){
            dp[i]=dp[i-1]+1
        }
        res = Math.max(res,dp[i])
    }
    return res
};

最长重复子数组

力扣题目链接

1. dp数组含义：
   二维数组；
   dp[i][j]: 以nums1[i-1] ，nums2[j-1]结尾的最长重复子数组（注意为什么用i-1,j-1结尾？因为这样的话，）
2. 递推公式：
   当nums1[i-1]=nums2[j-1]时，
   dp[i][j]=dp[i-1][j-1]+1
3. 初始化：
   dp[i][0],dp[0][j]=0
4. 遍历顺序
   顺序
5. 打印dp数组

var findLength = function(nums1, nums2) {
  let dp=new Array(nums1.length+1).fill(0).map(ele=>{ //注意+1，因为从i-1开始的
      return new Array(nums2.length+1).fill(0)
  })

 let res=0
  for(let i=1;i<=nums1.length;i++){
      for(let j=1;j<=nums2.length;j++){
          if(nums1[i-1]===nums2[j-1]){
              dp[i][j]=dp[i-1][j-1]+1
          }
        res=Math.max(res,dp[i][j])
      }
  }
  return res
};