一、课上练习

编程练习

1. 方格取数：L3441

二、知识总结

✨ 核心思想

方格取数问题是一类典型的动态规划问题，通常涉及在一个矩形网格中，按照特定的规则移动，并在路径上尽可能多地收集分布在网格中的数值。

问题定义：

• 给定一个 n×m 的网格，每个格子中有一个非负整数
• 起始位置在左上角 (1,1)，终止位置在右下角 (n,m)
• 每次只能向右或向下移动
• 目标是找到一条路径，使得路径上的数值总和最大

✨ 动态规划解法

状态定义

用 dp[i][j] 表示从起点 (1,1) 到位置 (i,j) 的最大数值总和。

状态转移方程

dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]

其中 grid[i][j] 是网格中位置 (i,j) 的数值。到达 (i,j) 只能从上方或左方过来，取两者中较大的即可。

边界条件

起点 dp[1][1] = grid[1][1]，第一行只能从左方到达，第一列只能从上方到达。

计算顺序

从左上角到右下角逐步计算 dp 值，确保在计算 dp[i][j] 时，dp[i-1][j] 和 dp[i][j-1] 已经计算完成。

1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7int maxPathSum(vector<vector<int>>& grid) {
8    int n = grid.size();
9    int m = grid[0].size();
10
11    // 创建dp数组并初始化
12    vector<vector<int>> dp(n, vector<int>(m, 0));
13    dp[0][0] = grid[0][0];
14
15    // 初始化第一行
16    for (int j = 1; j < m; ++j) {
17        dp[0][j] = dp[0][j - 1] + grid[0][j];
18    }
19
20    // 初始化第一列
21    for (int i = 1; i < n; ++i) {
22        dp[i][0] = dp[i - 1][0] + grid[i][0];
23    }
24
25    // 填充dp数组
26    for (int i = 1; i < n; ++i) {
27        for (int j = 1; j < m; ++j) {
28            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
29        }
30    }
31
32    // 返回右下角的最大值
33    return dp[n - 1][m - 1];
34}
35
36int main() {
37    vector<vector<int>> grid = {
38        {5, 3, 2, 1},
39        {1, 2, 10, 1},
40        {4, 3, 2, 20}
41    };
42
43    int result = maxPathSum(grid);
44    cout << "The maximum path sum is: " << result << endl;
45
46    return 0;
47}

✨ 执行示例

以 3x4 的网格为例，追踪 dp 表的填充过程：

网格 grid:
5  3  2  1
1  2  10 1
4  3  2  20

第 1 步：初始化起点

• dp[0][0] = grid[0][0] = 5

第 2 步：填充第一行（只能从左边来）

• dp[0][1] = dp[0][0] + 3 = 8
• dp[0][2] = dp[0][1] + 2 = 10
• dp[0][3] = dp[0][2] + 1 = 11

第 3 步：填充第一列（只能从上面来）

• dp[1][0] = dp[0][0] + 1 = 6
• dp[2][0] = dp[1][0] + 4 = 10

第 4 步：填充其余位置

最终答案：dp[2][3] = 42

对应的最优路径：(0,0)→(0,1)→(0,2)→(1,2)→(2,2)→(2,3)，即 5+3+2+10+2+20=42。

✨ 解题步骤详解

解决方格取数问题的步骤：

1. 确认移动规则：只能向右或向下（确保不会走回头路）
2. 定义状态：dp[i][j] = 从起点到 (i,j) 的最大路径和
3. 处理边界：第一行只能从左边来，第一列只能从上面来，用累加初始化
4. 逐行逐列填表：dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]
5. 读取答案：右下角 dp[n-1][m-1] 即为最大路径和

✨ 常见错误

1. 边界初始化遗漏：第一行和第一列必须单独用累加方式初始化，不能直接用转移方程（因为不存在 dp[i-1][j] 或 dp[i][j-1]）
2. 下标从 0 还是 1 开始搞混：如果题目坐标从 1 开始，而代码数组从 0 开始，需要注意偏移
3. 方向搞反：如果题目要求从右下到左上，需要调整计算顺序
4. 忘记加当前格子的值：转移方程中必须加上 grid[i][j]
5. 空间优化时覆盖了需要的数据：如果用一维数组优化，要注意遍历顺序

✨ 算法评价

• 时间复杂度：O(n×m)，需要遍历整个网格来计算每个位置的最大数值总和
• 空间复杂度：O(n×m)，用于存储 dp 数组。可以优化为 O(min(n,m))，通过只保留当前行和上一行的值

✨ 扩展思考

• 路径记录：如果需要记录路径，可以在 dp 的基础上再加一个 parent 数组，存储每一步是从哪个方向来的
• 其他移动方式：可以扩展到允许其他移动方向（如上、左），只需调整状态转移方程
• 多次访问：若每个格子可以多次访问，则问题会变得更复杂，需要不同的处理方式

三、课后练习

编程练习

1. 三角形最佳路径问题：L3442