KK's blog

每天积累多一些

0%

DP

Posted on Edited on Disqus:
  • 典型递归式
  • 单序列或匹配型DP模板
  • 数值到个数DP模板(最常考)
  • 区间型DP模板
  • 压缩空间
  • 打印路径

典型递归式：

单序列型(与一个或多个前状态有关)
硬币个数(数值型)： dp[i] = min(dp[i], dp[i - j] + 1)
偷房子： dp[i] = max(dp[i-1], dp[i-2] + nums[i - 1])
LIS： dp[i] = max(dp[i], dp[j] + 1) 1 <= j < i
Work break： dp[i] |= dp[j] and s[j:i] in word_set, 0 <= j < i

坐标型DP(与上、左等两个前状态有关)

1
dp[n][m] = max{1, min(dp[n+1][m], dp[n][m+1]) - dungeon[n][m]}

匹配型(与上、左、左上等三个前状态有关)

1
2
正则： dp[i][j] = dp[i-1][j-1] && (p[j-1] == . || s[i-1] == p[j-1])
OR ((dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == .)) || dp[i][j-2]) && p[j-1] == *

区间型(与该区间内以k为划分的两个子区间有关)

1
dp[i][j] = max{dp[i][m] + nums[i]×nums[m]×nums[j] + dp[m][j]}, i < m < j

多状态型DP(DP有多个终止状态)

1
2
3
4
5
dp = dp     if s[i] = '0'
   = dp + 1 if s[i] = '1'
   
dp2 = min(dp2 + 1, dp + 1)     if s[i] = '0'
    = min(dp2, dp)             if s[i] = '1'

解题步骤：

9zhang按照DP四部曲

  1. [初始化]dp数组
  2. [实现]
  3. [答案]
  4. [优化]是否可以用滚动内存优化空间

单序列或匹配型DP模板

实现注意事项(5点)：

  1. [多1][初始化]初始化矩阵，dp是原长度加1。因为令边界计算方便. 遍历从多少开始，取决于前状态多少个，若递归式含dp[i-1],从1开始，如果dp[i-2]就从2开始.数值型DP，如硬币个数DP长度是数值amount，不是数组长度。Python用dp = [[0 for _ in range(M)] for _ in range(N)], M为col数，再row数
  2. [特殊初始值]是第一步的完善，若一维初始化dp0，若为矩阵，初始化dp[0][0]以及上和左边界。求个数dp[0] = 1, 求最值, dp[0] = 0因为递归式含+1
  3. [多1]跳过初始值，i从1循环到len(dp)而不是len(s), 因为用了dp[0]占位。若不用占位法，就要用if语句判断第一位的边界。大部分递归式含i-1项，所以绝大部分从1开始，从什么开始取决于递归式，这也受第二步的影响
  4. [少1]用到原数组s时候是s[i - 1]而不是s[i], 因为用了dp[0]占位。实现时候递归式和条件要合法，保证边界内，如dp[i - t] => i - t >=0和s[i - 1 - dp[i - 1] - 1]，见最长括号数
  5. [答案]不一定是dp[-1]，如果以某位结束的答案而不是累积结果，一般就用max_len

累积DP递归公式

1
dp[n] = max(dp[n - 1], f)

Python代码：

1
2
3
4
5
6
def dp(self, s):
	dp = [False] * (len(s) + 1)
	dp[0] = True
	for i in range(1, len(dp)):
		...
	return dp[-1]

算法分析：

时间复杂度为O(n)，空间复杂度O(n)。

应用题型：

LeetCode 139 Word Break
LeetCode 044 Wildcard Matching
LeetCode 010 Regular Expression Matching

数值到个数DP模板(最常考)

求个数DP是比较简单的DP，但也是比较常考的。一般DP是前n个，这里是用数值，这点还是有点难的。

递归公式

1
dp[n + num[i]] = dp[n], n = [1, tgt], i = [0, len(nums) - 1]

注意事项：

  1. dp[i + nums[j]] += dp[i] 而不是dp[i] + 1
  2. dp[0] = 1表示数值为0，可以不用任何数就能获得，所以是1种
  3. i从0开始，因为此题递归式用相加i + nums[j]，而不是相减
  4. nums先排序，否则如[3, 1, 2, 4]，返回dp[1] = 0, 但应该是dp[1] = 1
  5. 上述4点注意事项只有1和2。数
1
2
3
4
5
6
7
8
9
10
def dp(self, nums, target):
	nums.sort() # remember
	dp = [0] * (target + 1)
	dp[0] = 1 # remember
	for i in range(len(dp)):
		for j in range(len(nums)):
			if i + nums[j] > target:
				break
			dp[i + nums[j]] += dp[i] # remember no +1
	return dp[-1]

应用题型：

LeetCode 377 Combination Sum IV

一个变体是求最小个数

递归公式

1
dp[n + coins[i]] = min{dp[n + coins[i]], dp[n] + 1}, n = [1, tgt], i = [0, len(nums) - 1]

不同之处：

  1. 递归式是dp[i] + 1
  2. dp初始值为最大值，而且dp[0] = 0
1
2
3
4
5
6
7
8
9
10
def dp(self, coins: List[int], amount: int) -> int:
	coins.sort()
	dp = [float('inf')] * (amount + 1)
	dp[0] = 0
	for i in range(len(dp)):
		for j in range(len(coins)):
			if i + coins[j] > amount:
				break
			dp[i + coins[j]] = min(dp[i + coins[j]], dp[i] + 1)
	return dp[-1] if dp[-1] < float('inf') else -1  # remember

应用题型：

LeetCode 322 Coin Change
LeetCode 871 Minimum Number of Refueling Stops

算法分析：

时间复杂度为O(n*target)，空间复杂度O(n)。

区间型DP模板

k循环从1还是从2开始取决于递归式

1
2
3
4
5
6
7
def dp(self, s: str) -> int:
	# init dp array
	for k in range(1, len(s)):
		for i in range(len(s) - k):
			j = i + k
			# dp formula
	return dp[0][-1]

应用题型：

LeetCode 516 Longest Palindromic Subsequence
LeetCode 312 Burst Balloons

压缩空间

若递归式和上一行有关，绝大部分属于此情况，就可以用两行，原数量列来处理

与标准模板不同之处：

  1. 行个数为2
  2. i仍然是遍历到所有行，所以不能用len(dp),而是len(text1) + 1.
  3. dp行不用i，而是i % 2
1
2
3
4
5
6
7
8
9
def longestCommonContinuous(self, text1: str, text2: str) -> int:
	dp = [[0 for _ in range(len(text2) + 1)] for _ in range(2)]
	res = 0
	for i in range(1, len(text1) + 1):
		for j in range(1, len(dp[0])):
			if text1[i - 1] == text2[j - 1]:
				dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + 1
				res = max(res, dp[i % 2][j])
	return res

应用题型：

Karat 002 Longest Common Continuous Subarray
LeetCode 063 Unique Paths II

打印路径

三种类型：

  1. LCA: Karat 002 Longest Common Continuous Subarray res = history1[i - dp[i][j]:i]
  2. LIS:
    LeetCode 300 Longest Increasing Subsequence
    LeetCode 368 Largest Divisible Subset
  3. LCS: LeetCode 1143 Longest Common Subsequence

LIS过程：

  1. path跟dp数组一样大，记录回溯跳转j -> i路径path[i - 1] = j - 1
  2. 记录回溯开始点if res == dp[i]: biggest_pos = i - 1
  3. 循环长度为res, 从biggest_pos开始

Python代码：

1
2
3
4
5
6
def print_path(self, nums, path[:biggest_pos + 1], dp_value = res):
	pos, res = len(path) - 1, []
	for _ in range(dp_value):
		res.append(nums[pos])
		pos = path[pos]
	return res[::-1]

LCS:

  1. path和dp一样，不用特别数组
  2. 从右下到左上，若上或左值一样，向此方向移动，直到左和上少一，此时res -= 1

Python代码：

1
2
3
4
5
6
7
8
9
10
11
longest, res = dp[-1][-1], ''
while m >= 0 and n >= 0:
	if dp[m - 1][n] == longest:
		m -= 1
	elif dp[m][n - 1] == longest:
		n -= 1
	else:
		res += text1[m - 1]
		longest -= 1
		m -= 1
		n -= 1
Free mock interview