动态规划基础：从斐波那契到数塔问题
动态规划，简称 DP。很多初学者一听这名字就头大。说实话，我当年学的时候也懵——这玩意儿到底「动态」在哪？
后来做项目多了才明白，动态规划其实就是一种「聪明的穷举」。它不暴力求解，而是把大问题拆成小问题，再把小问题的答案记下来，避免重复计算。
嗯，今天我们就从最基础的概念讲起。你跟着我走一遍，会发现 DP 其实没那么玄乎。
动态规划的核心要素
要理解 DP，先记住两个关键词：最优子结构和重叠子问题。
最优子结构
什么叫最优子结构？说白了就是：大问题的最优解，可以由小问题的最优解推导出来。
举个例子。你想从北京到上海，走最短路径。如果你经过济南，那么北京到济南这一段，也必须是北京到济南的最短路径。否则你整体就不可能是最短的。
这就是最优子结构——子问题的最优解，是全局最优解的一部分。
判断标准：如果你能写出递推公式，那大概率就具备最优子结构。
重叠子问题
这个更好理解。你想想看，如果一个问题拆成子问题后，这些子问题被反复计算，那就是重叠子问题。
我举个例子你就明白了——斐波那契数列。
典型问题一：斐波那契数列
斐波那契数列的定义很简单：
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) (n ≥ 2)很多教材一上来就写递归。但我要告诉你——纯递归是灾难。
为什么？我们画个图看看。
看到没？F(3) 被算了两次，F(2) 被算了三次。n 越大，重复越恐怖。我算过，n=50 时递归调用次数超过 200 亿——你的电脑直接卡死。
那怎么办？把算过的结果存起来。这就是 DP 的精髓。
自底向上的写法
#include <stdio.h>
long long fib(int n) {
if (n <= 1) return n;
long long dp[n+1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];
}
int main() {
printf("F(50) = %lld\n", fib(50));
return 0;
}这个版本，n=50 瞬间出结果。为什么？因为每个子问题只算一次。
小技巧：如果只关心最后结果，可以只用两个变量滚动更新，不用整个数组。空间从 O(n) 降到 O(1)。
典型问题二：数塔问题
数塔问题，是理解 DP 的经典入门题。题目是这样的：
有一个数字三角形，从顶部出发，每次只能走到下一层的相邻节点。求从顶部到底部的最大路径和。
5
/ \
8 3
/ \ / \
9 7 1
/ \ / \ / \
4 6 8 2从 5→8→7→6 这条路径，和是 26。但还有没有更大的？
我刚开始做这题时，第一反应是 DFS 遍历所有路径。但仔细一想——每层两个选择，n 层就是 2^(n-1) 条路径。n=50 时，宇宙毁灭都算不完。
那 DP 怎么解？
状态定义
定义 dp[i][j] 表示从第 i 行第 j 列走到最底部的最大路径和。
状态转移方程
dp[i][j] = triangle[i][j] + max(dp[i+1][j], dp[i+1][j+1])什么意思？从 (i,j) 出发，可以往左下 (i+1,j) 或右下 (i+1,j+1)。选大的那个走。
代码实现
#include <stdio.h>
#define MAX_N 100
int max(int a, int b) {
return a > b ? a : b;
}
int maxPathSum(int triangle[][MAX_N], int n) {
// dp数组，从底部往上推
int dp[MAX_N][MAX_N] = {0};
// 初始化最后一行
for (int j = 0; j < n; j++) {
dp[n-1][j] = triangle[n-1][j];
}
// 从倒数第二行开始往上推
for (int i = n-2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
dp[i][j] = triangle[i][j] + max(dp[i+1][j], dp[i+1][j+1]);
}
}
return dp[0][0];
}
int main() {
int triangle[][MAX_N] = {
{5},
{8, 3},
{9, 7, 1},
{4, 6, 8, 2}
};
printf("最大路径和: %d\n", maxPathSum(triangle, 4));
return 0;
}运行结果：最大路径和是 26？不对，我算出来是 5+8+9+8=30。你仔细看看，5→8→9→8 这条路径，确实存在。
注意：数塔问题中，路径必须相邻。不能跳着走。我见过有人把 5→3→7→8 也算进去，那是不对的。
动态规划的一般步骤
做 DP 题，我习惯按这四步走：
- 定义状态——dp[i][j] 表示什么？想清楚再动手。
- 找转移方程——当前状态怎么从前面的状态推出来？
- 确定初始值——边界条件是什么？比如 dp[0][0] 是多少？
- 确定遍历顺序——是从上往下，还是从下往上？
这四步，缺一不可。我曾经在项目里写 DP 时，状态定义没想清楚就开写，结果 debug 了一下午。后来学乖了——先在纸上画一遍，再敲代码。
总结一下
动态规划不是什么神秘的东西。它就是一种「记忆化搜索」——把算过的结果存起来，避免重复劳动。
判断一个问题能不能用 DP，就看两点：
- 最优子结构：大问题能拆成小问题，且小问题的最优解能拼成大问题的最优解。
- 重叠子问题：小问题会被反复计算。
如果满足这两点，DP 就是你的最佳选择。
斐波那契数列和数塔问题，是 DP 的「Hello World」。把这两个吃透，后面再学背包问题、最长公共子序列，就会轻松很多。
嗯，今天就到这儿。代码不多，但概念很重要。你最好自己动手敲一遍，光看是学不会 DP 的。