1143.最长公共子序列
文章讲解/视频讲解
题目描述：
给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。
一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。
例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。
若这两个字符串没有公共子序列，则返回 0。
示例 1:
- 输入：text1 = "abcde", text2 = "ace"
- 输出：3
- 解释：最长公共子序列是 "ace"，它的长度为 3。
示例 2:
- 输入：text1 = "abc", text2 = "abc"
- 输出：3
- 解释：最长公共子序列是 "abc"，它的长度为 3。
示例 3:
- 输入：text1 = "abc", text2 = "def"
- 输出：0
- 解释：两个字符串没有公共子序列，返回 0。
提示:
- 1 <= text1.length <= 1000
- 1 <= text2.length <= 1000 输入的字符串只含有小写英文字符。
思路：
本体难于昨天的“718.最长重复子数组”，因为这里不要求是连续的了，但是还是得保持相对顺序的。
1.确定dp数组及其下标含义：dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]。
这里不方便定义长度为[0, i-1]长度的字符串，昨天说过了，这样不方便后续代码实现
2.确定递推公式：只存在两种情况： text1[i - 1] 与 text2[j - 1]相同和text1[i - 1] 与 text2[j - 1]不相同
如果 text1[i - 1] 与 text2[j - 1]相同，那么很不错，因为我们直接找到了一个公共元素，让dp[i][j] = dp[i - 1][j - 1] + 1即可
那么如果text1[i - 1] 与 text2[j - 1]不相同，我们就得比较text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取最大的。我们要么不考虑text[i - 1]这个字符，要么不考虑text[j - 1]这个字符，但是总得选一个，因为两者都不用的情况（dp[i - 1][j - 1]）其实已经被这前两种情况包含了。
3.dp数组如何初始化：全部初始化为0即可
4.确定遍历顺序：我们一共有三个方向可以推出dp[i][j]，如图：
那么为了在递推的过程中，这三个方向都是经过计算的数值，所以要从前向后，从上到下来遍历这个矩阵。
5.举例推导dp数组
以输入：text1 = "abcde", text2 = "ace" 为例，dp状态如图：
最后红框dp[text1.size()][text2.size()]为最终结果
代码示例：
function longestCommonSubsequence(text1: string, text2: string): number { const length1: number = text1.length const length2: number = text2.length const dp: number[][] = new Array(length1 + 1).fill(0).map(_ => new Array(length2 + 1).fill(0)) for (let i = 1; i <= length1; i++) { for (let j = 1; j <= length2; 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[length1][length2] };1035.不相交的线
文章讲解/视频讲解
题目描述：
在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足：
- nums1[i] == nums2[j]
- 且绘制的直线不与任何其他连线（非水平线）相交。
请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。
以这种方法绘制线条，并返回可以绘制的最大连线数。
思路：
本题上来一看就容易懵逼，但是换个思路理解一下会很简单，所谓的连线不能相交其实就是要在字符串nums1中找到与字符串nums2相同的子序列，而且子序列不能改变顺序，也就是如果nums1中找到的是1，4，那么你nums2中就不能找4，1，只要顺序保持一致，就没问题，那么这不就是我们刚写的最长公共子序列吗？一写还真是，代码都一模一样的，只需要把数组名一改即可。
代码示例：
function maxUncrossedLines(nums1: number[], nums2: number[]): number { const length1:number = nums1.length const length2:number = nums2.length const dp:number[][] = new Array(length1 + 1).fill(0).map(_ => new Array(length2 + 1).fill(0)) for(let i = 1; i <= length1; i++){ for(let j = 1; j <= length2; 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][j - 1], dp[i - 1][j]) } } } return dp[length1][length2] };53.最大子数组和
文章讲解/视频讲解
题目描述：
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
- 输入: [-2,1,-3,4,-1,2,1,-5,4]
- 输出: 6
- 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
思路：
本题之前用贪心的思路写过一次，今天来用动态规划的思维再解决一次这个问题，直接开始动规五部曲
1.确定dp数组及其下标含义：dp[i]：以nums[i]为结尾（包括下标i）的最长子数组和
2.确定递推公式：本题的递推公式只能从两个方向推出来：要么计算nums[i] + dp[i - 1]的和，要么直接从nums[i]开始，所以我们要对比二者，不断更新其中最大的。即dp[i] = max(dp[i - 1] + nums[i], nums[i])
3.dp数组如何初始化：由递推公式可以得出，dp[0]就是递推公式的基础，根据定义来看，dp[0]显然就等于nums[0]（小心不要错误赋值成0了）
4.确定遍历顺序：从递推公式来看，本题一定是从前往后遍历的。
5.举例推导dp数组
以示例一为例，输入：nums = [-2,1,-3,4,-1,2,1,-5,4]，对应的dp状态如下：
注意最后的结果可不是dp[nums.size() - 1]！，而是dp[6]。
在回顾一下dp[i]的定义：包括下标i之前的最大连续子序列和为dp[i]。
那么我们要找最大的连续子序列，就应该找每一个i为终点的连续最大子序列。
所以在递推公式的时候，可以直接选出最大的dp[i]。
代码示例：
function maxSubArray(nums: number[]): number { const length:number = nums.length if(length === 1) return nums[0] const dp:number[] = new Array(length) let resMax:number = dp[0] = nums[0] for(let i = 1; i < length; i++){ dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]) if(dp[i] > resMax){ resMax = dp[i] } } return resMax };392.判断子序和
文章讲解/视频讲解
题目描述：
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
示例 1：
- 输入：s = "abc", t = "ahbgdc"
- 输出：true
示例 2：
- 输入：s = "axc", t = "ahbgdc"
- 输出：false
提示：
- 0 <= s.length <= 100
- 0 <= t.length <= 10^4
两个字符串都只由小写字符组成。
思路：
本题属于编辑距离的入门题，因为我们只需要考虑删除t字符串中的字符，不用考虑添加，替换
1.确定dp数组及其下标含义：dp[i][j] 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为dp[i][j]。这里注意s的长度是小于等于t的。
2.确定递推公式：本题的dp[i][j]同样只能从两个方向推出来，要么遍历到当前s[i - 1] === t[j - 1]，那么我们直接dp[i - 1][j - 1] + 1即可，与刚刚的题思路保持一致。但是如果s[i - 1] !== t[j - 1]了，我们就只考虑删除t字符，因为t的长度大于s，不可能删s的字符的，而所谓的删除其实就是比较i - 1 和 j - 2，也就是dp[i][j] = dp[i][j - 1](因为dp[i][j]分别对应下标i - 1和下标j - 1结尾)
3.dp数组的初始化：由于dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]，所以dp[0][0]和dp[i][0]是一定要初始化的。全部初始化为0
4.确定遍历顺序：由递推公式可得，从上往下，从左往右遍历
如图所示：
5. 举例推导dp数组：
以示例一为例，输入：s = "abc", t = "ahbgdc"，dp状态转移图如下：
dp[i][j]表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t 相同子序列的长度，所以如果dp[s.size()][t.size()] 与 字符串s的长度相同说明：s与t的最长相同子序列就是s，那么s 就是 t 的子序列。
图中dp[s.size()][t.size()] = 3， 而s.size() 也为3。所以s是t 的子序列，返回true。
代码示例：
function isSubsequence(s: string, t: string): boolean { const slen:number = s.length const tlen:number = t.length const dp:number[][] = new Array(slen + 1).fill(0).map(_ => new Array(tlen + 1).fill(0)) for(let i = 1; i <= slen; i++){ for(let j = 1; j <= tlen; 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[slen][tlen] === slen };
