1143.最长公共子序列
力扣链接
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列（未必连续） 的长度。如果不存在 公共子序列 ，返回 0 。
思路
- 确定dp含义
dp[i][j]：长度为[0,i-1]和[0,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]的最长公共子序列，取最大的。
即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
if (text1[i - 1] == text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
- 初始化
全部初始化为0 - 确定遍历方向
从前向后，从上向下
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
dp = [ [0]*(len(text2)+1) for _ in range(len(text1)+1) ]
for i in range(1, len(text1)+1):
for j in range(1, len(text2)+1):
if text1[i-1]==text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i][j-1], dp[i-1][j])
return dp[-1][-1]
1035.不相交的线
力扣链接
我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。
现在，我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且我们绘制的直线不与任何其他连线（非水平线）相交。
以这种方法绘制线条，并返回我们可以绘制的最大连线数。
思路
这就是说明在字符串A中 找到一个与字符串B相同的子序列，且这个子序列不能改变相对顺序，只要相对顺序不改变，链接相同数字的直线就不会相交。
代码和上一题一样！
53. 最大子序和
力扣链接
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
思路
- 确定dp含义
dp[i]：以nums[i]结尾的连续数组最大和为i - 确定递推公式
最大和要么是nums[i]，要么是dp[i-1]+nums[i]，取个max
dp[i]=max(nums[i],dp[i-1]+nums[i])
- 初始化
dp[0]=nums[0]，其余随便 - 确定递推方向
从前到后
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
dp = [0] * len(nums)
dp[0] = nums[0]
for i in range(1,len(nums)):
dp[i] = max(nums[i],dp[i-1]+nums[i])
return max(dp)
392.判断子序列
力扣链接
给定字符串 s 和 t ，判断 s 是否为 t 的子序列。(可以不连续）
思路
- 确定dp数组
以下标i-1结尾的字符串s和下标j-1结尾的字符串t，相同子序列长度为dp[i][j] - 确定递推公式
如果s[i - 1] == t[j - 1]，dp[i][j] = dp[i-1][j-1] + 1
否则，dp[i][j] = dp[i][j-1] - 初始化
全初始化为0 - 确定遍历方向
从上到下，从左到右。
代码与最长公共子序列的差不多。
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
dp = [ [0]*(len(t)+1) for _ in range(len(s)+1) ]
for i in range(1, len(s)+1):
for j in range(1, len(t)+1):
if s[i-1]==t[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i][j-1], dp[i-1][j])
return dp[-1][-1]==len(s)
