Base Case 与备忘录初始值的确定
本文通过一道经典 DP 题「下降路径最小和」讲解 base case、备忘录初始值和边界返回值的确定方法。
题目以 ACM 格式 给出：从标准输入读取数据，输出最小路径和。
题目描述
问题描述
给定一个 n × n 的方形整数矩阵，从第一行中的任意元素开始，每次可以移动到下一行的正下方、左下方或右下方（即 (row+1, col-1), (row+1, col), (row+1, col+1)）。
求从第一行走到最后一行的最小路径和。
输入格式
- 第一行一个整数
n，表示矩阵的边长。 - 接下来
n行，每行n个整数，表示矩阵元素。
输出格式
一个整数，表示最小下降路径和。
输入样例 1
3
2 1 3
6 5 4
7 8 9
输出样例 1
13
输入样例 2
2
-19 57
-40 -5
输出样例 2
-59
数据范围
1 ≤ n ≤ 100-100 ≤ matrix[i][j] ≤ 100
解题思路（动态规划标准套路）
1. 定义 dp 函数
我们定义 dp(i, j) 表示：从第一行向下落，落到位置 matrix[i][j] 的最小路径和。
根据这个定义，最终答案就是最后一行的最小值：
answer = min(dp(n-1, 0), dp(n-1, 1), ..., dp(n-1, n-1))
2. 状态转移方程
对于 matrix[i][j]，它只能从上一行的三个位置转移而来：
(i-1, j)(i-1, j-1)(i-1, j+1)
因此状态转移方程为：
dp(i, j) = matrix[i][j] + min( dp(i-1, j), dp(i-1, j-1), dp(i-1, j+1) )
3. 暴力递归（不考虑重叠子问题）
int dp(vector<vector<int>>& matrix, int i, int j) {
// 非法索引检查
if (i < 0 || j < 0 || i >= matrix.size() || j >= matrix[0].size()) {
return INT_MAX; // 返回一个特殊的大值
}
// base case
if (i == 0) {
return matrix[i][j];
}
// 状态转移
return matrix[i][j] + min({dp(matrix, i - 1, j),
dp(matrix, i - 1, j - 1),
dp(matrix, i - 1, j + 1)});
}
4. 带备忘录的优化（消除重叠子问题）
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> memo; // 备忘录
int dp(vector<vector<int>>& matrix, int i, int j) {
// 1. 索引合法性检查
if (i < 0 || j < 0 || i >= matrix.size() || j >= matrix[0].size()) {
return INT_MAX;
}
// 2. base case
if (i == 0) {
return matrix[0][j];
}
// 3. 查备忘录
if (memo[i][j] != 66666) {
return memo[i][j];
}
// 4. 状态转移
memo[i][j] = matrix[i][j] + min({dp(matrix, i - 1, j),
dp(matrix, i - 1, j - 1),
dp(matrix, i - 1, j + 1)});
return memo[i][j];
}
int main() {
int n;
cin >> n;
vector<vector<int>> matrix(n, vector<int>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> matrix[i][j];
}
}
// 初始化备忘录：用 66666 表示未计算（该值大于最大可能路径和 10000）
memo = vector<vector<int>>(n, vector<int>(n, 66666));
int res = INT_MAX;
for (int j = 0; j < n; ++j) {
res = min(res, dp(matrix, n - 1, j));
}
cout << res << endl;
return 0;
}
三个关键问题
以上代码虽然正确，但初学者常常对以下三个细节感到困惑：
- base case 为什么是
i == 0？返回值为什么是matrix[0][j]？ - 备忘录
memo的初始值为什么是66666？可以用别的值吗？ - 对于非法索引（越界），为什么返回
INT_MAX？
下面逐一解答。
一、base case 的条件如何确定？
回顾 dp(i, j) 的定义：从第一行落到 (i, j) 的最小路径和。
- 当
i == 0时，我们已经在第一行了，要落到(0, j)的路径和就是该位置本身的值matrix[0][j]。 - 所以 base case 就是
i == 0时返回matrix[0][j]。
原则：base case 由 dp 函数的定义直接得出，它对应递归树的最底层、不需要再依赖子问题的状态。
二、备忘录的初始值如何确定？
备忘录 memo[i][j] 用来存储 dp(i, j) 的计算结果。初始值必须是一个不可能与任何合法答案混淆的特殊值，这样才能判断该状态是否已经计算过。
题目给出的数据范围：
1 <= n <= 100-100 <= matrix[i][j] <= 100
合法路径经过 n 个格子，每个格子最小 -100，最大 100，所以：
- 最小可能路径和 =
100 * (-100) = -10000 - 最大可能路径和 =
100 * 100 = 10000
因此，合法答案的区间是 [-10000, 10000]。
备忘录的初始值只要避开这个区间即可，比如 66666（大于 10000），或者 -99999（小于 -10000），甚至 INT_MAX / INT_MIN。
注意：如果使用
INT_MAX作为初始值，要小心INT_MAX + 正数会溢出。这里只是用来判断是否计算过，不会对它做加法，所以安全。
结论： 特殊值的选择依赖于题目给出的数据范围，确保不与任何可能答案冲突。
三、边界情况的返回值如何确定？
当索引越界时（比如 j-1 变成负数，或 j+1 超出列数），dp 函数应该返回什么？
看状态转移方程：
dp(i, j) = matrix[i][j] + min( dp(i-1, j), dp(i-1, j-1), dp(i-1, j+1) )
我们调用的是 min 函数，希望不合法的子问题不被选中。因此，对于越界的子问题，应该返回一个足够大的值，使得 min 永远不会选中它。
合法答案最大为 10000，所以返回任何 大于 10000 的值（如 INT_MAX 或 99999）即可。
如果题目要求的是最大值（如最长路径），那么越界时应返回一个足够小的值（如
INT_MIN）。
原则：
- 求最小值时，非法状态返回
+∞（一个大数） - 求最大值时，非法状态返回
-∞（一个小数）
延伸：从题目信息中挖掘解题线索
除了确定特殊值，题目的数据范围和时间复杂度限制还能给我们其他提示：
1. 数据范围估算复杂度
- 如果
n <= 20，可能支持指数级的搜索（DFS/回溯）。 - 如果
n <= 1000，通常需要O(n^2)或O(n^2 log n)的算法。 - 如果
n <= 10^5，大概率需要O(n log n)或O(n)。
本题 n <= 100，O(n^3) 也能勉强通过，但用备忘录 DP 的 O(n^2) 更优。
2. 时间复杂度限制暗示算法结构
- 要求
O(N log N)：暗示用到二分搜索或堆/优先队列（如 Dijkstra）。 - 要求
O(MN)：暗示二维 DP 或二维前缀和。 - 要求
O(N^2)：可能是区间 DP 或 LCS 等问题。
虽然猜测不一定 100% 准确，但当你完全没有思路时，这些信息可以帮你缩小思考范围。
总结
| 问题 | 确定原则 | 本题取值 |
|---|---|---|
| base case | 根据 dp 函数的定义，当无法继续分解时直接返回 | i == 0 时返回 matrix[0][j] |
| 备忘录初始值 | 必须与所有合法答案不同，通常取区间外的值 | 66666（大于 10000） |
| 非法索引返回值 | 求最小和时返回 +∞，求最大和时返回 -∞ | INT_MAX |
牢记这三点，动态规划的状态定义与边界处理将不再困惑你。
多留意题目给出的数据范围和时间复杂度限制，它们往往是解题的“暗号”。