动态规划

算法

139. 单词拆分

  1. 题意: 判断一个 s 能不能由一个 wordDict 组成
  2. 思路: 一维动态规划
    1. dp[i]: s[0:i]是否能被组成
    2. 对于每个 dp[i], 去找有没有一个分割位置j能够让前半部分能被组成且后半部分在字典中
  3. 代码:
1
2
3
4
5
6
7
8
9
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
    wordSet = set(wordDict) # 小优化
    dp = [False]*(len(s)+1)
    dp[0] = True # 空串能被组成
    for i in range(1, len(s)+1):
        for j in range(0, i):
            if dp[j]==True and s[j:i] in wordSet:
                dp[i] = True
    return dp[len(s)]

300. 最长递增子序列

  1. 题意: 找无需连续的最长递增长度
  2. 思路: 一维动态规划
    1. dp[i]: 以 num[i] 为结尾的最长长度 (初始值为 1)
    2. 对于每个dp[i], 去找 [0, i-1]范围内比自己 num 小的 dp 最大值 + 1
  3. 代码:
1
2
3
4
5
6
7
def lengthOfLIS(self, nums: List[int]) -> int:
    dp = [1]*len(nums)
    for i in range(len(nums)):
        for j in range(0, i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j]+1)
    return max(dp)

42. 接雨水

  1. 思路: (动态规划版)
    1. 对于每个索引，求左侧最高柱子高度和右侧最高柱子高度 (包括自己!)
    2. 对于每个索引，其最大储水量: 左右柱子取较小值 - 当前柱子高度 (特判负数!)
  2. 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def trap(self, height: List[int]) -> int:
	# 1. DP (包括自己)
	max_left = [0]*len(height)
	max_right = [0]*len(height)
	max_left[0] = height[0]
	for i in range(1, len(height)):
		max_left[i] = max(max_left[i-1], height[i])
	max_right[-1] = height[-1]
	for i in range(len(height)-2, -1, -1):
		max_right[i] = max(max_right[i+1], height[i])
	# 2. 求和 (注意负值)
	water = 0
	for i in range(1, len(height)-1):
		water += max(0, min(max_left[i], max_right[i])-height[i])
	return water

5. 最长回文子串

  1. 题意: 找到给定字符串中的最长回文子串(连续), 返回子串
  2. 思路: 二维动态规划
    1. dp[i][j]: s[i:j+1] 是否为回文串 (i, j 相当于左右边界)
    2. 初始:
      1. 当 i==j 时, 就是单个字符, 肯定为 True
      2. 当 i+1==j 时, 就是两个字符, 判断 s[i]==s[j]
    3. 转移:
      1. dp[i][j]取决于两个条件:
        1. s[i]==s[j] (边界是否相等)
        2. dp[i+1][j-1] (除开左右边界, 内部的是否为回文串)
      • i 需要从下往上遍历 (转移时主要关注左下角的状态, 画个草图即可理解)
    4. 最后答案需要遍历一下 dp 二维数组, 找到最长的回文子串
  3. 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def longestPalindrome(self, s: str) -> str:
	n = len(s)
	dp = [ [False]*n for _ in range(n)]
	for i in range(n): # i==j
		dp[i][i] = True
	for i in range(n-1): # i+1==j
		dp[i][i+1] = s[i]==s[i+1]
	for i in range(n-3, -1, -1): # 其他情况
		for j in range(i+2, n):
			dp[i][j] = s[i]==s[j] and dp[i+1][j-1]
	max_s = ''
	for i in range(n): # 额外遍历
		for j in range(i, n):
			if dp[i][j] and j-i+1 > len(max_s):
				max_s = s[i:j+1]
	return max_s

516. 最长回文子序列

  1. 题意: 找到给定字符串中的最长回文子序列(不连续), 返回长度
  2. 思路: 二维动态规划
    1. dp[i][j]: s[i:j+1] 内的最长回文子序列的长度 (i, j 相当于左右边界)
    2. 初始:
      1. 当 i==j 时, 就是单个字符, 肯定为 True
      2. 当 i+1==j 时, 就是两个字符, 判断 s[i]==s[j]
    3. 转移:
      1. 当 s[i]==s[j], dp[i][j] = dp[i+1][j-1] + 2
      2. 当 s[i]!=s[j], dp[i][j] = max(dp[i][j-1], dp[i+1][j])
  3. 代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def longestPalindromeSubseq(self, s: str) -> int:
    n = len(s)
    dp = [ [None]*n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1
    for i in range(n-1):
        dp[i][i+1] = 2 if s[i]==s[i+1] else 1
    for i in range(n-3, -1, -1):
        for j in range(i+2, n):
            if s[i]==s[j]:
                dp[i][j] = dp[i+1][j-1] + 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    return dp[0][n-1]