动态规划标志：
二维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
70
71
72
73
74
75
| def max_path(grid):
dp = [[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]
dp[0][0] = grid[0][0]
for i in range(1, len(grid[0])):
dp[0][i] = dp[0][i - 1] + grid[0][i]
for j in range(1, len(grid)):
dp[j][0] = dp[j - 1][0] + grid[j][0]
for i in range(1, len(grid)):
for j in range(1, len(grid[0])):
dp[i][j] = grid[i][j] + max(dp[i-1][j], dp[i][j-1])
return dp[-1][-1]
def max_path_loop(grid: List[List]) -> int:
"""
Point is that, when optimize space complexity for 2d dp array, we can only optimize 2d to 1d array.
注意观察 3 Mention commented in the code
优化原理：
一句话概括： dp变成了滚动数组。
首先， 对于二维dp中每一个格子i, j的计算， 我们需要的只有三个数： 1. up， 2. left， 3. grid中的i,j 的值
那么， 只要优化后的一维数组 能够记录到 1 & 2 ， 则可计算 出 i， j的值。
只用一维数组怎么表示i，j的值？
第一层循环的for row in rows， 就相当于表示了i， 而j， 则是第二层循环的col表示。
怎么用一维dp记录的 上下两个维度的数？
滚动数组， 当遍历到dp_oned[col]时， 当前的dp_oned[col] 的值， 还是记录着 dp[i-1][j]的值， 但是dp_oned[col-1]已经被更新成了dp[i][j-1]了。
那二维dp中的第一行怎么办？
初始 dp_oned 为 grid[0]
那最上面一行， 最左侧一列的数怎么办？ 这一行/一列的数据， 没有上面/左侧的格子。
看Mention 2
具体讲：
首先， 优化后的一维 dp， 相当于先记录了 原2维dp的第一行所有数，然后变成 第二行， ....
其次， 对于优化后的一维dp， 其每一个元素都对应着原dp中的一个i, j， 再dp[j]被更新之前， 它还保存着 原dp[i-1, j]的值。 同时， 由于是从左到右不停的 遍历dp。
这意味着 当 遍历到 dp[j]的时候， dp[j] 左边的格子 dp[j-1] 已经被更新， 即意味着其记录的值， 已经是原二维dp中的 i-1,j 这个格子的值了。
说话不好理解， 看例子：
懒的画。
只要记住， 对于每一次循环过程中， 再 col 变成 len(cols) - 1之前， 一维的dp中 既有 二维dp中 第i 行的值， 也有第 i-1 行的值。
而当一次 cols for结束， row从i 变为 i-1时， dp表示的行， 就从二维dp中的第i行变为第i+1行。
:param grid:
:return:
"""
cols = len(grid[0])
rows = len(grid)
dp = grid[0]
for row in range(rows):
for col in range(cols):
left_max = 0 if col == 0 else dp[col-1]
up_max = 0 if row == 0 else dp[col]
dp[col] = grid[row][col] + max(left_max, up_max)
return dp[-1]
|
Original by Shain at Mel, Australia
Last Updated: 2022/1/23