最长递增子序列
- dp数组含义：以nums[i]结尾的最长递增子序列
- 递推公式：dp[i]=max(dp[i],dp[j]+1)//若nums[j]<nums[i]
- 初始化：每一个i，对应的dp[i]（即最长递增子序列）起始大小至少都是1.
- 遍历顺序：从前向后遍历。后一个依赖前一个结果。
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)
与上题区别：连续。
只需要与前一个元素比较。
- dp数组含义：
dp[i] 为以nums[i]结尾的最长连续递增序列 - 递推公式：
若dp[i-1]<dp[i]
dp[i]=dp[i-1]+1，只需要与前一个元素比较，而不需要遍历i之前的元素。 - 初始化：
初始所有值=1，根据含义，以i结尾的序列，至少有一个元素 - 遍历顺序
顺序。 -
打印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
};
最长重复子数组
- dp数组含义：
二维数组；
dp[i][j]: 以nums1[i-1] ，nums2[j-1]结尾的最长重复子数组（注意为什么用i-1,j-1结尾？因为这样的话，） - 递推公式：
当nums1[i-1]=nums2[j-1]时，
dp[i][j]=dp[i-1][j-1]+1 - 初始化：
dp[i][0],dp[0][j]=0 - 遍历顺序
顺序 - 打印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
};
