最長公共子序列
- dp數(shù)組含義：
二維數(shù)組：
dp[i][j]: 以i-1,j-1結(jié)尾的最長公共子序列長度 - 遞推公式：
（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党饮，同最長重復(fù)子數(shù)組 - 遍歷順序
順序
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)
本質(zhì)是求最長公共子序列
代碼與其一致，故略郊供。
最大子序和
- dp數(shù)組含義：
dp:以i結(jié)尾的最大子序和 - 遞推公式：
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
};
