这几题都挺类似,都是求最长公共子序列,有些题目稍微变了下
1143.最长公共子序列
体会一下本题和 718. 最长重复子数组 的区别
视频讲解:https://www.bilibili.com/video/BV1ye4y1L7CQ
https://programmercarl.com/1143.最长公共子序列.html
/**
* @param {string} text1
* @param {string} text2
* @return {number}
*/
var longestCommonSubsequence = function(text1, text2) {
const dp = new Array(text1.length+1).fill(0).map(()=>new Array(text2.length + 1).fill(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]);
}
}
}
return dp[text1.length][text2.length];
};
1035.不相交的线
其实本题和 1143.最长公共子序列 是一模一样的,大家尝试自己做一做。
视频讲解:https://www.bilibili.com/video/BV1h84y1x7MP
https://programmercarl.com/1035.不相交的线.html
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var maxUncrossedLines = function(nums1, nums2) {
const dp = new Array(nums1.length+1).fill(0).map(()=>new Array(nums2.length + 1).fill(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;
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[nums1.length][nums2.length];
};
- 最大子序和
这道题我们用贪心做过,这次 再用dp来做一遍
视频讲解:https://www.bilibili.com/video/BV19V4y1F7b5
https://programmercarl.com/0053.最大子序和(动态规划).html
/**
* @param {number[]} nums
* @return {number}
*/
var maxSubArray = function(nums) {
const dp = new Array(nums.length);
dp[0] = nums[0];
let max = nums[0];
for (let i=1;i<nums.length;i++) {
dp[i] = Math.max(dp[i-1]+nums[i], nums[i]);
if (dp[i] > max) {
max = dp[i];
}
}
return max;
};
392.判断子序列
这道题目算是 编辑距离问题 的入门题目(毕竟这里只是涉及到减法),慢慢的,后面就要来解决真正的 编辑距离问题了
https://programmercarl.com/0392.判断子序列.html
/**
* @param {string} s
* @param {string} t
* @return {boolean}
*/
var isSubsequence = function(s, t) {
const dp = new Array(s.length+1).fill(0).map(()=>new Array(t.length + 1).fill(0));
for (let i=1;i<=s.length;i++) {
for (let j=1;j<=t.length;j++) {
if (s[i-1] === t[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = dp[i][j-1];
}
}
}
return dp[s.length][t.length] === s.length ? true : false;
};
标签:1143,随想录,param,length,https,序列,new,com,dp
From: https://www.cnblogs.com/yuanyf6/p/18277177