算法动态规划

棋盘DP

字数统计: 1.7k字   |   阅读时长: 7分
,

摘要: 棋盘 DP 的题目总结

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在很多时候，我们要在矩阵或者三角形上解决问题。比如给定一个矩阵，求最大的子矩阵和；又比如给定一个三角形，求从第一行走到最后一行的最小路径和。

因为问题的场景类似于一个网格，与棋盘很像，这类问题如果能够找到动态规划的解法，并且推导过程是沿着矩阵的行和列线性地推导的，我们经常称其为棋盘 DP。

对于这种棋盘 DP 的问题，如果 $i$ 是行号、$j$ 是列号，状态表示一般定义为 $dp[i][j]$。状态的转移方程需要根据实际问题，找到阶段的划分方式再进行推导。有两类常见的阶段划分方式：

第一种是每一步必须向下走一步，左右的走法比较自由。此时行数 $i$ 作为阶段，从当前状态到下一阶段的状态，意味着从第 $i$ 行到了第 $i+1$ 行，而列数 $j$ 是作为阶段的附加状态存在的。按照 $i$ 从小到大线性推导状态即可。

第二种是只能向右走一步或向下走一步，此时以到源点的曼哈顿距离 $i+j$ 作为阶段，从当前状态推导到下一阶段的状态，意味着从横纵坐标之和（到左上角的距离）加 1。状态表示中的 $(i, j)$ 隐含了阶段，同时包含了所需的附加信息，也就是 $i + j$ 步当中有多少步是向右走的。按照 $i$ 从小到大，$j$ 从小到大线性推导状态即可。

本文我们给这两种常见的阶段划分方式都整理了一些例题，然后给出了题目的动态规划算法，可以作为集中练习使用。这里首先给一个题目总览：

行号 $i$ 作为阶段，$(i, j)$ 为状态表示

120. 三角形最小路径和

1
2
3
4
5
6
7
8
9
10
11
12
状态定义：
dp[i][j] := 从 (0, 0) 走到 (i, j) 的最小路径和

答案：
min(dp[n - 1][j])

初始化：
dp[0][0] = grid[0][0]
dp[i][0] = grid[i][j] + dp[i - 1][0]

状态转移：
dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i - 1][j - 1])

931. 下降路径最小和

1
2
3
4
5
6
7
8
9
10
11
状态定义：
dp[i][j] := 以 (i, j) 为起点可以取到的最小和

答案：
min(dp[0][j])

初始化：
dp[n - 1][j] = A[n - 1][j]

状态转移：
dp[i][j] = A[i][j] + min(dp[i + 1][j], dp[i + 1][j - 1], dp[i + 1][j + 1])

1289. 下降路径最小和 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
状态定义：
dp[i][j] := 走到 (i, j) 可以得到的最小和

答案：
min(dp[n - 1][j])

初始化：
dp[0][j] = arr[0][j]

状态转移：
dp[i][j] = a[i][j] + min(dp[i - 1][k])
其中 k != j

优化：
推导时顺便记录每一阶段(每个 i)的最小值，次小值，即 min(dp[i][j]), submin(dp[i][j])

799. 香槟塔

1
2
3
4
5
6
7
8
9
10
11
12
13
状态定义：
dp[i][j] := 第 i 行第 j 个杯子的量

答案：
min(dp[n][m], 1.0)

初始化：
dp[0][0] = S

状态转移:
dp[i][0] = 1/2 * (dp[i - 1][1] - 1)
dp[i][i] = 1/2 * (dp[i - 1][i - 1] - 1)
dp[i][j] = 1/2 * (dp[i - 1][j] - 1) + 1/2 * (dp[i - 1][j - 1] - 1)

$i+j$ 作为阶段，$(i, j)$ 为状态表示

64. 最小路径和 / 剑指 Offer 47. 礼物的最大价值

1
2
3
4
5
6
7
8
9
10
11
12
13
状态定义：
dp[i][j] := 从 (0, 0) 走到 (i, j) 的最小路径和

答案：
dp[n - 1][m - 1]

初始化：
dp[0][0] = grid[0][0]
dp[0][j] = grid[0][j] + dp[0][j - 1]
dp[i][0] = grid[i][0] + dp[i - 1][0]

状态转移：
dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1])

1301. 最大得分的路径数目

1
2
3
4
5
6
7
8
9
10
11
12
状态定义：
dp[i][j] := 从 (0, 0) 到 (i, j) 的最大和

答案：
dp[n - 1][m - 1]

初始化：
dp[0][0] = 0

状态转移：
dp[i][j] = max(dp[i - 1][i - 1], dp[i][j - 1], dp[i - 1][j]) + board[i][j]
其中 i > 0, j > 0, board[i][j] 不是障碍

1594. 矩阵的最大非负积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
状态定义：
dp_max[i][j] := 从 (0, 0) 走到 (i, j) 的最大的路径乘积
dp_min[i][j] := 从 (0, 0) 走到 (i, j) 的最小的路径乘积

答案：
dp_max[n - 1][m - 1]

初始化：
dp_max[0][0] = grid[0][0];
dp_min[0][0] = grid[0][0];
其余均为 0

状态转移：
若 grid[i][j] > 0:
    dp_max[i][j] = max(dp_max[i - 1][j] * grid[i][j], dp_max[i][j - 1] * grid[i][j]);
    dp_min[i][j] = min(dp_min[i - 1][j] * grid[i][j], dp_min[i][j - 1] * grid[i][j]);
若 grid[i][j] < 0:
    dp_max[i][j] = max(dp_min[i - 1][j] * grid[i][j], dp_min[i][j - 1] * grid[i][j]);
    dp_min[i][j] = min(dp_max[i - 1][j] * grid[i][j], dp_max[i][j - 1] * grid[i][j]);

174. 地下城游戏

1
2
3
4
5
6
7
8
9
10
11
12
状态定义：
dp[i][j] := 从 (i, j) 到 (n - 1, m - 1) 所需初始点数

答案：
dp[0][0]

初始化：
dp[n - 1][m - 1] = max(1, 1 - dungeon[n - 1][m - 1]);

状态转移：
dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]);
其中 i < n - 1, j < m - 1

221. 最大正方形

1
2
3
4
5
6
7
8
9
10
11
12
状态定义：
dp[i][j] := 以 (i + 1, j + 1) 为右下角的最大正方形的边长

答案：
max(dp[i][j]) * max(dp[i][j])

初始化：
dp[i][j] = 0

状态转移：
dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
其中 grid[i - 1][j - 1] 为 1

1277. 统计全为 1 的正方形子矩阵

1
2
3
4
5
6
7
8
9
10
11
状态定义：
dp[i][j] := 以 (i, j) 为右下角的最大正方形的边长

答案：
sum(dp[i][j])

初始化：
dp[i][j] = A[i][j] == 1

状态转移：
dp[i][j] = 1 + min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]);
Share