数字三角形与数字矩形:两类最经典的棋盘DP状态设计

  |  

摘要: 数字三角形问题

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


本文我们通过数字三角形和数字矩形这两个简单问题来看一下棋盘 DP 的两类基本设计思路。

在棋盘 DP 的问题中,比较常见的有两种行动方式,一种是只能向右走一步或向下走一步;另一种是必须向下走一步,左右的走法比较自由。矩形最小路径和对应的是第一种,数字三角形问题对应的是第二种。

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

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


数字三角形问题

120. 三角形最小路径和

给定一个三角形 triangle ,找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标 i 或 i + 1 。

提示:

1
2
3
4
1 <= triangle.length <= 200
triangle[0].length == 1
triangle[i].length == triangle[i - 1].length + 1
-104 <= triangle[i][j] <= 104

示例 1:
输入:triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出:11
解释:如下面简图所示:
2
3 4
6 5 7
4 1 8 3
自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。

示例 2:
输入:triangle = [[-10]]
输出:-10

进阶:

你可以只使用 $O(n)$ 的额外空间(n 为三角形的总行数)来解决这个问题吗?

动态规划

数字三角形是棋盘场景线性 DP 的基础问题,其状态表示为 $dp[i][j]$,表示从左上角走到 $(i, j)$ 的路径最小的和。

阶段划分为路径的结尾行数,阶段推导一次,意味着行数 +1。而阶段并不足以表示状态,状态表示是需要列号信息的,因此列号为附加信息作为状态的一个维度。

在状态 $(i, j)$ 处考虑,它有可能从前一阶段的 $(i - 1, j)$ 或 $(i - 1, j - 1)$ 转移而来,因此状态转移方程为:

完整算法如下:

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

答案
max(dp[n - 1][...])

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

状态转移
dp[i][j] = a[i][j] + max(dp[i - 1][j], dp[i - 1][j - 1])

代码 (python)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
n = len(triangle)
m = len(triangle[0])
dp = [[0 for _ in range(m)] for _ in range(n)]
dp[0][0] = triangle[0][0];
for i in range(1, n):
for j in range(m):
dp[i][j] = dp[i - 1][j]
if j > 0:
dp[i][j] = max(dp[i][j], dp[i - 1][j - 1])
dp[i][j] += triangle[i][j]
return dp[n - 1][m - 1]

数字矩形问题

最小路径和

给定一个包含非负整数的 m x n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

说明:每次只能向下或者向右移动一步。

提示:

1
2
3
4
m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 200

示例 1:
输入:grid = [[1,3,1],[1,5,1],[4,2,1]]
输出:7
解释:因为路径 1→3→1→1→1 的总和最小。

示例 2:
输入:grid = [[1,2,3],[4,5,6]]
输出:12

算法:动态规划

矩形三角形是棋盘场景线性 DP 的基础问题,其状态表示为 $dp[i][j]$,表示从左上角走到 $(i, j)$ 的路径最小的和。

阶段划分为到源点的曼哈顿距离 $i + j$,阶段推导一次,意味总距离 +1。而阶段并不足以表示状态,状态表示是需要行号信息的。状态表示的两个维度 $(i, j)$ 隐含了阶段以及所需的附加信息。

在状态 $(i, j)$ 处考虑,它有可能从前一阶段的 $(i - 1, j)$ 或 $(i, j - 1)$ 转移而来,因此状态转移方程为:

完整算法如下:

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

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

初始化:
dp[0][0] = grid[0][0]

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

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
n = len(grid)
m = len(grid[0])
INF = int(1e6)
dp = [[INF for _ in range(m)] for _ in range(n)]
dp[0][0] = grid[0][0];
for i in range(n):
for j in range(m):
if i == 0 and j == 0:
continue
if i > 0:
dp[i][j] = min(dp[i][j], dp[i - 1][j])
if j > 0:
dp[i][j] = min(dp[i][j], dp[i][j - 1])
dp[i][j] += grid[i][j]
return dp[n - 1][m - 1]

Share