在哪几个网站里做自媒体赚钱,用博客网站做淘宝客,工具大全,阜城网站建设价格【代码随想录训练营】【Day 52】【动态规划-11】| Leetcode 1143, 1035, 53#xff0c;392
需强化知识点
题目
1143. 最长公共子序列
注意还是要从0-i-1, 0-j-1 定义#xff0c;因为我们需要遍历 0
class Solution:def longestCommonSubsequence(self, text1: str, text…【代码随想录训练营】【Day 52】【动态规划-11】| Leetcode 1143, 1035, 53392
需强化知识点
题目
1143. 最长公共子序列
注意还是要从0-i-1, 0-j-1 定义因为我们需要遍历 0
class Solution:def longestCommonSubsequence(self, text1: str, text2: str) - int:m, n len(text1), len(text2)# 0-i-1, 0-j-1 的最长公共序列长度dp [[0]*(n1) for _ in range(m1)]result 0for i in range(1, m1):for j in range(1, n1):if text1[i-1] text2[j-1]:dp[i][j] dp[i-1][j-1]1else:dp[i][j] max(dp[i][j-1], dp[i-1][j])result max(result, dp[i][j])return result
1035. 不相交的线
同上的思路
class Solution:def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) - int:m, n len(nums1), len(nums2)# 0-i-1, 0-j-1 的 相交数量dp [[0] * (n1) for _ in range(m1)]result 0for i in range(1, m1):for j in range(1, n1):if nums1[i-1] nums2[j-1]:dp[i][j] dp[i-1][j-1] 1else:dp[i][j] max(dp[i-1][j], dp[i][j-1])result max(result, dp[i][j])return result392. 判断子序列
编辑距离初级题
class Solution:def isSubsequence(self, s: str, t: str) - bool:m, n len(s), len(t)# 0-i-1,0-j-1 的子序列长度dp [[0] * (n1) for _ in range(m1)]for i in range(1, m1):for j in range(1, n1):if s[i-1] t[j-1]:dp[i][j] dp[i-1][j-1] 1else:dp[i][j] dp[i][j-1]if dp[m][n] m:return Trueelse:return False
