代码随想录算法训练营19期第53天

1143.最长公共子序列 

视频讲解：动态规划子序列问题经典题目 | LeetCode：1143.最长公共子序列_哔哩哔哩_bilibili

代码随想录

初步思路：动态规划。

总结：

dp[i][j] ：长度为[0, i - 1]的字符串A与长度为[0, j - 1]的字符串B的最长公共子序列为dp[i][j]

If (A[i - 1] == B[j - 1]):     dp[i][j] = dp[i - 1][j - 1] + 1

Else:                                     dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

用时：30分钟

 1035.不相交的线 

视频讲解：动态规划之子序列问题，换汤不换药 | LeetCode：1035.不相交的线_哔哩哔哩_bilibili

代码随想录

初步思路：动态规划。

总结：

求绘制的最大连线数，其实就是求两个字符串的最长公共子序列的长度！

用时：45分钟

 53. 最大子序和 

视频讲解：看起来复杂，其实是简单动态规划 | LeetCode：53.最大子序和_哔哩哔哩_bilibili

代码随想录

初步思路：动态规划

总结：

dp[i]：包括下标i（以nums[i]为结尾）的最大连续子序列和为dp[i]

dp[i] = max(dp[i - 1] + nums[i], nums[i])

用时：30分钟