算法动态规划

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

字数统计: 1.5k字   |   阅读时长: 6分
,

摘要: 数字三角形问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的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
-1e4 <= triangle[i][j] <= 1e4

示例 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