最长公共子序列
- dp数组含义：
二维数组：
dp[i][j]: 以i-1,j-1结尾的最长公共子序列长度 - 递推公式：
（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]) - 初始化：
均为0，同最长重复子数组 - 遍历顺序
顺序
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)
本质是求最长公共子序列
代码与其一致，故略。
最大子序和
- dp数组含义：
dp:以i结尾的最大子序和 - 递推公式：
dp[i]=max(dp[i-1]+nums[i],nums[i]) - 初始化：
dp[0]=nums[0],其余为0 - 遍历顺序
顺序
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
};
