【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总（1）https://developer.aliyun.com/article/1536617
经典题目
*最长回文子串
# 动态规划 # 用 P(i,j)P(i,j) 表示字符串 s的第 i 到 j 个字母组成的串（下文表示成 s[i:j]）是否为回文串 class Solution: def longestPalindrome(self, s: str) -> str: n = len(s) dp = [[False] * n for _ in range(n)] ans = "" # 枚举子串的长度 l+1 for l in range(n): # 枚举子串的起始位置 i，这样可以通过 j=i+l 得到子串的结束位置 for i in range(n-l): j = i + l if l == 0: dp[i][j] = True elif l == 1: dp[i][j] = (s[i] == s[j]) else: dp[i][j] = (dp[i + 1][j - 1] and s[i] == s[j]) if dp[i][j] and l + 1 > len(ans): ans = s[i:j+1] return ans # 中心扩展法 class Solution: def expandAroundCenter(self, s, left, right): while left >= 0 and right < len(s) and s[left] == s[right]: left -= 1 right += 1 return left + 1, right - 1 def longestPalindrome(self, s: str) -> str: # 中心扩展法，每个字符从中心往两边扩展，分奇偶 start, end = 0, 0 for i in range(len(s)): left1, right1 = self.expandAroundCenter(s, i, i) # 以当前字符为中心 left2, right2 = self.expandAroundCenter(s, i, i + 1) # 以当前字符与后面一个字符为中心 if right1 - left1 > end - start: start, end = left1, right1 if right2 - left2 > end - start: start, end = left2, right2 return s[start: end + 1]
*最长有效括号
法一：动态规划
class Solution: def longestValidParentheses(self, s: str) -> int: # 动态规划 # dp[i] 表示以i结尾的最长有效括号长度，‘（’对应的一定是0 n = len(s) if n == 0: return 0 dp = [0] * n for i in range(1,n): # i- dp[i-1] -1是与当前')'对称的位置 # dp[i-dp[i-1]-2] 表示与当前')'对称的位置前面的有效括号长度，需加上 if s[i]==')' and i - dp[i-1] - 1>=0 and s[i - dp[i-1] - 1] == '(': dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2 return max(dp)
法二：栈
class Solution: def longestValidParentheses(self, s: str) -> int: # 栈来实现 stack = [-1] length = 0 max_length = 0 for i in range(len(s)): if s[i] == '(': stack.append(i) else: stack.pop() if not stack: # 栈为空，则添加当前右括号的索引入栈，为分割标识 stack.append(i) else: length = i - stack[-1] max_length = max(max_length, length) return max_length
*不同的子序列
class Solution: def numDistinct(self, s: str, t: str) -> int: # S中T出现的个数 # dp[i][j]表示t的前i个字符串可以由s的前j个字符串组成多少个 n = len(s) # 列 m = len(t) # 行 dp = [[0] * (n+1) for _ in range(m+1)] for j in range(n+1): dp[0][j] = 1 for i in range(1,m + 1): for j in range(1, n + 1): if t[i-1] == s[j-1]: # 对应于两种情况，s选择当前字母和不选择当前字母 # s选择当前字母dp[i-1][j-1] # s不选择当前字母 dp[i][j-1] dp[i][j] = dp[i-1][j-1] + dp[i][j-1] else: dp[i][j] = dp[i][j-1] return dp[-1][-1]
*最长公共子序列
# 动态规划 class Solution: def longestCommonSubsequence(self, text1: str, text2: str) -> int: m = len(text1) n = len(text2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(1, m+1): for j in range(1, n+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] # 递归 class Solution: def longestCommonSubsequence(self, text1: str, text2: str) -> int: # 递归 memo = {} #备忘录 def dp(i, j): if i == -1 or j == -1: return 0 if (i,j) in memo: return memo[(i,j)] if text1[i] == text2[j]: memo[(i,j)] = dp(i-1, j-1) + 1 else: memo[(i,j)] = max(dp(i-1, j), dp(i,j-1)) return memo[(i,j)] return dp(len(text1)-1,len(text2)-1)
*最长公共子串
注意：与子序列不相同的是子串是连续的，子序列可以是不连续的。
def LCS(s1,s2): #dp[i][j]表示以s1的i及s2的j结尾的最长公共子串长度 #如果s1[i-1] ！= s2[j-1] 则，dp[i][j] = 0 m = len(s1) n = len(s2) dp = [[0] *(n+1) for _ in range(m + 1)] maxLen = 0 end = 0 for i in range(1,m+1): for j in range(1,n+1): if s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1] + 1 else: dp[i][j] = 0 if dp[i][j] > maxLen: maxLen = dp[i][j] end = j-1 if maxLen == 0: return '' else: return s2[end - maxLen + 1:end + 1]
*最长上升子序列
class Solution: def lengthOfLIS(self, nums: List[int]) -> int: if not nums: return 0 # dp[i]表示以第i个元素结尾的最长递增子序列长度 n = len(nums) dp = [1 for _ in range(n)] for i in range(n): for j in range(i): if nums[i] > nums[j]: dp[i] = max(dp[i],dp[j] + 1) return max(dp)
**编辑距离
class Solution: def minDistance(self, word1: str, word2: str) -> int: # DP递推方程 # 存储 s1[0..i] 和 s2[0..j] 的最小编辑距离 m = len(word1) n = len(word2) dp = [[0]*(n+1) for i in range(m+1)] for i in range(m+1): dp[i][0] = i for j in range(n+1): dp[0][j] = j for i in range(1, m+1): for j in range(1,n+1): if word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1) return dp[m][n] # 递归写法 class Solution: def minDistance(self, word1: str, word2: str) -> int: def dp(i,j): if i == -1: return j + 1 if j == -1: return i + 1 if (i,j) in memo: return memo[(i,j)] if word1[i] == word2[j]: memo[(i,j)] = dp(i-1,j-1) else: memo[(i,j)] = min(dp(i-1,j)+ 1, dp(i,j-1) + 1, dp(i-1,j-1) + 1) return memo[(i,j)] memo = {} res = dp(len(word1)-1,len(word2)-1) return res
最长重复子数组
class Solution: def findLength(self, A: List[int], B: List[int]) -> int: # p[i][j] 表示 A[i:] 和 B[j:] 的最长公共前缀，那么答案即为所有 dp[i][j] 中的最大值。 # 如果 A[i] == B[j]，那么 dp[i][j] = dp[i + 1][j + 1] + 1，否则 dp[i][j] = 0。 # 考虑到这里 dp[i][j] 的值从 dp[i + 1][j + 1] 转移得到，所以我们需要倒过来，首先计算 dp[len(A) - 1][len(B) - 1]，最后计算 dp[0][0] n, m = len(A), len(B) dp = [[0] * (m + 1) for _ in range(n + 1)] ans = 0 for i in range(n - 1, -1, -1): for j in range(m - 1, -1, -1): dp[i][j] = dp[i + 1][j + 1] + 1 if A[i] == B[j] else 0 ans = max(ans, dp[i][j]) return ans
完全平方数
class Solution: def numSquares(self, n: int) -> int: dp = [0] * (n + 1) for i in range(1, n + 1): dp[i] = i #最坏的情况就是全是1 j = 1 while i - j*j >= 0: dp[i] = min(dp[i], dp[i - j * j] + 1) j += 1 return dp[n]
【42页动态规划学习笔记分享】动态规划核心原理详解及27道LeetCode相关经典题目汇总（3）https://developer.aliyun.com/article/1536620
