0%

leetcode: DP

最大化网格幸福感

给你四个整数 m、n、introvertsCount 和 extrovertsCount 。有一个 m x n 网格,和两种类型的人:内向的人和外向的人。总共有 introvertsCount 个内向的人和 extrovertsCount 个外向的人。

请你决定网格中应当居住多少人,并为每个人分配一个网格单元。 注意,不必 让所有人都生活在网格中。

思路

每个点都有三种状态:不住人、住内向的人或者住外向的人。

1.状态压缩DP,由于矩阵大小n比较小,用长度为n的三进制数字记录每一行的状态,一共有种状态,预先计算出行内和行间不同状态间的得分变化。再进行回溯就可以,回溯的单位是行,每次选择的范围是。因此时间复杂度为

2.插头DP(轮廓线DP),记录上一行当前元素到这一行j - 1个元素一共n个元素的状态,可以在时间算出行内和行间得分。进行记忆化搜索就可以,搜索的单位是每个点,每次选择的范围是3,时间复杂度是

实现

第一种:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
def getMaxGridHappiness_matrix_dp(self, m: int, n: int, ic: int, ec: int) -> int:
NO, IC, EC = 0, 1, 2

def line_extra(cur, prev):
if cur == NO or prev == NO:
return 0
if cur == IC and prev == IC:
return -60
if cur == EC and prev == EC:
return 40
return -10

# 当前行状态数量,每个格子是3种,所以是3 ** 6
state_n = 3 ** n
# 用来方便的计算下面的1和2
mask = [[0] * n for _ in range(state_n)]
# 1.mask的状态对应的ic和ec数量
ic_count = [0 for _ in range(state_n)]
ec_count = [0 for _ in range(state_n)]
# 2.mask的状态对应的行内和行间得分
line_score = [0 for _ in range(state_n)]
outline_score = [[0] * state_n for _ in range(state_n)]
# dp table
dp = [[[[-1] * (ec + 1) for _ in range(ic + 1)] for _ in range(m)] for _ in range(state_n)]

# 预先计算, O(3 ** n * n)
for i in range(state_n):
cur = i
j = 0
while cur != 0 and j <= n:
mask[i][j] = cur % 3
cur //= 3
j += 1
for j in range(n):
# 计算ic和ec数量以及行内得分
if mask[i][j] != NO:
if mask[i][j] == IC:
ic_count[i] += 1
line_score[i] += 120
elif mask[i][j] == EC:
ec_count[i] += 1
line_score[i] += 40
if j > 0: # 计算行内相邻得分
line_score[i] += line_extra(mask[i][j], mask[i][j - 1])
# 计算行间得分,O(3 ** n * 3 ** n * n)
for i in range(state_n):
for i2 in range(i, state_n):
for j in range(n):
outline_score[i][i2] += line_extra(mask[i][j], mask[i2][j])
outline_score[i2][i] = outline_score[i][i2]

# O(3 ** n * 3 ** n * m * ic * ec)
def dfs(last_mask, row, ic, ec):
if row == m or ic + ec == 0:
return 0
if dp[last_mask][row][ic][ec] != -1:
return dp[last_mask][row][ic][ec]
# 做选择
best = 0
for state in range(state_n):
# 剪枝
if ic_count[state] > ic and ec_count[state] > ec:
break
if ic_count[state] > ic or ec_count[state] > ec:
continue
score = line_score[state] + outline_score[state][last_mask]
best = max(best, score + dfs(state, row + 1, ic - ic_count[state], ec - ec_count[state]))
dp[last_mask][row][ic][ec] = best
return best

return dfs(0, 0, ic, ec)

第二种:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
def getMaxGridHappiness(self, m: int, n: int, ic: int, ec: int) -> int:
# 插头DP(轮廓线DP)
first = lambda x: x // (3 ** (n - 1))
last = lambda x: x % 3
x = lambda pos: pos / n
y = lambda pos: pos % n
NO, IC, EC = 0, 1, 2

# 预先计算
state_n = 3 ** n
elements = {}
n_states = {}
for i in range(state_n):
f, l = first(i), last(i)
elements[i] = (f, l)
remain = i % (3 ** (n - 1))
n_states[i] = (remain * 3 + NO, remain * 3 + IC, remain * 3 + EC)


# 在位置pos出,选择为choice,轮廓线状态为state的得分,O(1)
def cur_score(pos, state, choice):
c_x, c_y = x(pos), y(pos)
p_1, p_2 = elements[state]
res = line_extra(choice, p_1) # 与上方邻居的额外得分
if c_y > 0:
res += line_extra(choice, p_2) # 与左侧邻居之间的额外得分
return res

# 更新轮廓线状态,O(1)
def next_state(state, choice):
return n_states[state][choice]

def line_extra(cur, prev):
if cur == NO or prev == NO:
return 0
if cur == IC and prev == IC:
return -60
if cur == EC and prev == EC:
return 40
return -10

# O(3 ** n * m * ic * ec)
@lru_cache(None)
def dfs(pos, prev_states, ic, ec):
# 到达边界,后续score为0
if pos == m * n or ic + ec == 0:
return 0
# 做选择
# 在当前位置啥也不放
state = next_state(prev_states, NO)
best = 0 + dfs(pos + 1, state, ic, ec)
# 放一个内向的
if ic > 0:
state = next_state(prev_states, IC)
score = 120 + cur_score(pos, prev_states, IC)
best = max(best, score + dfs(pos + 1, state, ic - 1, ec))
# 放一个外向的
if ec > 0:
state = next_state(prev_states, EC)
score = 40 + cur_score(pos, prev_states, EC)
best = max(best, score + dfs(pos + 1, state, ic, ec - 1))
return best

return dfs(0, 0, ic, ec)

k个节点的覆盖集合最小代价

二叉树上找到一个k个节点组成的集合,使得每一条边都与该集合中至少一个节点相连接。

如果存在这样的集合,返回最小的代价,否则返回null。

思路

对二叉树中某个点i来说,要保证一定有边与它相连接,那么有两种状态:该点在集合中or该点不在集合中。

  • i未被选择且以i为根节点的子树满足要求时的最低cost和对应的节点weight,用dp[i][0]表示;
  • i被选择且以i为根节点的子树满足要求时的最低cost和对应的节点weight,用dp[i][1]表示。

实现

树形DP实现。时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
from typing import List

from Tree.BTree import Tree


def left_c(x):
return 2 * x + 1


def right_c(x):
return 2 * x + 2


class Solution:
def vertex_cover(self, tree: List, k: int):
n = len(tree)
if n < k:
return
dp = [[[0, []] for _ in range(2)] for _ in range(n)]

# O(|V| * k),需要对每个节点遍历一次,由于需要进行列表的extend操作O(len(list2))开销,所以上限开销为←。
def DP(curr: int):
# is_leaf = all([tree[child] == '#' for child in [left_c(curr), right_c(curr)]])
# 如果选当前节点或者不选当前节点的初始开销总和和weights
dp[curr][1] = [tree[curr], [tree[curr]]]
dp[curr][0] = [0, []]
for child in [left_c(curr), right_c(curr)]:
if child < n and tree[child] != '#': # 不为空节点
DP(child)
if dp[child][1][0] < dp[child][0][0]:
dp[curr][1][0] += dp[child][1][0]
dp[curr][1][1] += dp[child][1][1]
else:
dp[curr][1][0] += dp[child][0][0]
dp[curr][1][1] += dp[child][0][1]

dp[curr][0][0] += dp[child][1][0]
dp[curr][0][1] += dp[child][1][1]

DP(0) # 从root开始
cost, weights = dp[0][0] if dp[0][0] < dp[0][1] else dp[0][1]
if len(weights) > k: # 说明最小覆盖节点数要大于k,无法满足要求,返回None
return
if len(weights) == k: # 如果恰好满足要求,直接返回最小开销和
return cost

# O(|V|)
def traverse(curr: int):
if curr == '#':
return []
res = [tree[curr]]
left = traverse(left_c(curr)) if left_c(curr) < n and tree[left_c(curr)] != '#' else []
right = traverse(right_c(curr)) if right_c(curr) < n and tree[right_c(curr)] != '#' else []
return res + left + right

all_weights = traverse(0)
if len(all_weights) < k: # 这里是由于存储的方式的问题,所以要判断两次,这次判断的是|V|是否小于k
return
# O(|V| * k)
print(weights)
for weight in weights:
all_weights.remove(weight) # O(|V|)
# O(|V| * log|V|)
all_weights.sort()
# O(k)
while len(weights) < k:
weights.append(all_weights.pop(0))

return sum(weights)

Edit Distance

给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作:

插入一个字符
删除一个字符
替换一个字符

即NLP中计算编辑距离。

思路

使用递归式的自顶向下的动态规划,并增加重叠子问题的缓存。

自底向上的动态规划,1)状态数组存储的是的最小编辑距离,2)起始状态就是当其中一个数组为空,编辑距离是另一个数组的长度,3)计算当前时刻的状态值如果当前时刻字符不相等就选择增删改中最小的(进行了这些操作之后肯定会变成已知的一种状态)。

状态列表可以优化空间到O(m + n)。

实现

递归的方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
mem = {}
def helper(i, j):
key = '{}-{}'.format(i, j)
if i < 0: return j + 1
if j < 0: return i + 1
if key in mem:
return mem[key]
if word1[i] == word2[j]:
res = helper(i - 1, j - 1)

else:
res = min(
helper(i - 1, j - 1) + 1, # 替换
helper(i, j - 1) + 1, # 插入word1的单词
helper(i - 1, j) + 1 # 删除word1的单词
)
mem[key] = res
return res
return helper(len(word1) - 1, len(word2) - 1)

改写的迭代求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m, n = len(word1), len(word2)

dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)] # (m + 1) * (n + 1),多一个模拟i - 1
dp[0] = [j for j in range(n + 1)]
for i in range(m + 1):
dp[i][0] = i

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] + 1,
dp[i][j - 1] + 1,
dp[i - 1][j] + 1
)
return dp[m][n]

两种解法时间复杂度都是O(mn),空间复杂度第二种是O(mn)但是可以优化。

连通两组点的最小成本

给你两组点,其中第一组中有 size1 个点,第二组中有 size2 个点,且 size1 >= size2 。

任意两点间的连接成本 cost 由大小为 size1 x size2 矩阵给出,其中 cost[i][j] 是第一组中的点 i 和第二组中的点 j 的连接成本。如果两个组中的每个点都与另一组中的一个或多个点连接,则称这两组点是连通的。换言之,第一组中的每个点必须至少与第二组中的一个点连接,且第二组中的每个点必须至少与第一组中的一个点连接。

返回连通两组点所需的最小成本。

  • 1 <= size1, size2 <= 12

思路

首先,在搜索完整路径的情况下,某一个group中两个节点连接的顺序不影响最终的结果。一次选择随机一个节点进行连接就行。

直接DP的话会超时,所以把状态进行压缩用int的每一位来表示(长度不长),两个state每一位分别表示两个group中对应的节点是否已经连接,用位操作进行状态的判断和更新。

自顶向下的记忆化搜索。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
from functools import lru_cache


class Solution:
def connectTwoGroups(self, cost: List[List[int]]) -> int:
s1, s2 = len(cost), len(cost[0])
# 因为从group1开始选择,所以先记录group2中每个节点cost最小的选择
min_group_2 = [min(cost[i][j] for i in range(s1)) for j in range(s2)]

# DP[i, j]返回的是还有i和j代表状态的节点没有连接时的cost
# 自顶向下,DP[0, 0] = 0,记忆化搜索
# 因为每个组都必须要连接到另一个组里面的节点,所以先从节点多的组group1开始
# 每一次选择没有连接的一个点,并遍历所有可能的连接方式和记录ans
@lru_cache(None)
def dp(state1, state2):
if state1 == 0 and state2 == 0:
return 0
ans = float('inf')
if state1 != 0: # s1里面还有没有连接的点
for i in range(s1):
if state1 & (1 << i): # 第i个点还没有连接,对它向下递归遍历并跳出
for j in range(s2):
new_s1, new_s2 = state1 & ~(1 << i), state2 & ~(1 << j)
# 更新开销为所有选择下的最小开销
ans = min(ans, cost[i][j] + dp(new_s1, new_s2))
break
else: # group1已经选完了,group2里的节点直接选择预先记录的最小cost边就行
for j in range(s2):
if state2 & (1 << j):
new_s1, new_s2 = 0, state2 & ~(1 << j)
ans = min(ans, min_group_2[j] + dp(new_s1, new_s2))
break
return ans


state1, state2 = (1 << s1) - 1, (1 << s2) - 1
return dp(state1, state2)

树中距离之和

思路

首先进行第一次搜索,找到所有节点的子图节点到该节点的距离和以及包含的子图节点个数。

然后第二次DFS搜索,自顶向下用父节点的n_dis和子节点包含的子图节点数量更新距离和信息。

题目默认0可以作为根节点,但是因为是无向图,所以遍历的时候需要加上双向边信息并用set记录已遍历的节点。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
from collections import defaultdict

class Solution:
def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
edge = defaultdict(list)
# p = [-1 for _ in range(N)]
n_node = [0 for _ in range(N)]
n_dist = [0 for _ in range(N)]
for s, e in edges:
edge[s].append(e)
edge[e].append(s) # 默认0为根节点,但是无向图要记录双向信息
# p[e] = s

root = 0
visited = set()

def dfs(cur):
visited.add(cur)
if not edge[cur]:
n_node[cur] = 1
return 1, 0
n_node_cur, n_dist_cur = 1, 0
for each in edge[cur]:
if each not in visited:
n_node_c, n_dist_c = dfs(each)
n_node_cur += n_node_c
n_dist_cur += n_dist_c
n_dist_cur += n_node_cur - 1
n_node[cur] = n_node_cur
n_dist[cur] = n_dist_cur
return n_node_cur, n_dist_cur

dfs(root) # 第一次遍历,记录每个节点所在子图节点到该节点的距离
# print(f'{n_node}\n{n_dist}')

res = [0 for _ in range(N)]
visited = set()

# 第二次遍历,从顶向下,用父节点的n_dis和子节点包含的子图节点数量更新信息
def calcu_dis(cur, parent):
visited.add(cur)
n_dist_cur = parent - n_node[cur] + (N - n_node[cur]) if cur != root else parent
res[cur] = n_dist_cur
for each in edge[cur]:
if each not in visited:
calcu_dis(each, n_dist_cur)

calcu_dis(root, n_dist[root])
return res

交错字符串

给定三个字符串 s1s2s3,请你帮忙验证 s3 是否是由 s1s2 交错 组成的。

思路

dp[i][j] 表示s1[:i]和s2[:j]可以交错为s3[:i + j - 1]。

可以用滚动数组优化空间复杂度。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
n, m, x = len(s1), len(s2), len(s3)
if n + m != x: return False
# dp[i][j] 表示s1[:i]和s2[:j]可以交错为s3[:i + j - 1],空间O(m * n)
dp = [[True] * (m + 1) for _ in range(n + 1)]
# 边缘条件,O(m + n)
dp[0][0] = True
for nn in range(1, n + 1):
dp[nn][0] = dp[nn - 1][0] and (s1[nn - 1] == s3[nn - 1])
for mm in range(1, m + 1):
dp[0][mm] = dp[0][mm - 1] and (s2[mm - 1] == s3[mm - 1])

# O(n * m)
for nn in range(1, n + 1):
for mm in range(1, m + 1):
dp[nn][mm] = dp[nn - 1][mm] and (s1[nn - 1] == s3[nn - 1 + mm]) or dp[nn][mm - 1] and (s2[mm - 1] == s3[nn + mm - 1])
return dp[n][m]