最长公共子序列

力扣题目链接

1. dp数组含义：
   二维数组：
   dp[i][j]: 以i-1,j-1结尾的最长公共子序列长度
2. 递推公式：
   （1）若nums1[i-1] =nums2[j-1]:
   dp[i][j]=dp[i-1][j-1]+1
   (2) 若nums1[i-1] !=nums2[j-1]
   dp[i][j]=max(dp[i-1][j],dp[i][j-1])
3. 初始化：
   均为0，同最长重复子数组
4. 遍历顺序
   顺序

var longestCommonSubsequence = function(text1, text2) {
    let dp=new Array(text1.length+1).fill(0).map(ele=> new Array(text2.length+1).fill(0))

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

不相交的线

力扣题目链接(opens new window)
本质是求最长公共子序列
代码与其一致，故略。

最大子序和

力扣题目链接

1. dp数组含义：
   dp:以i结尾的最大子序和
2. 递推公式：
   dp[i]=max(dp[i-1]+nums[i],nums[i])
3. 初始化：
   dp[0]=nums[0],其余为0
4. 遍历顺序
   顺序

var maxSubArray = function(nums) {
    let dp= new Array(nums.length).fill(0)
    dp[0]=nums[0]
    let res=nums[0]

    for(let i=1;i<nums.length;i++){
        dp[i]=Math.max(dp[i-1]+nums[i],nums[i])
        res=Math.max(res,dp[i])
    }
    return res
};