别重复思考——把答案写进表格，后面的题直接"抄作业"
你每天做同一类数学题，有两种做法：暴力法——每道都从头算，哪怕昨天刚算过一模一样的；聪明法——准备一个作业本（一张表），把算过的答案抄在本子上，遇到重复的子题直接抄作业。第 5 题要用到第 4 题和第 3 题的结果？本子上现成的，拿过来用。动态规划（DP，Dynamic Programming）就是"作业本算法"：把大问题拆成小问题，小问题的答案记在数组里，大问题站在小问题的肩膀上。
DP 不神秘，它只回答三个问题：① 表格每格是什么意思（状态）？② 每格怎么从前面的格子算出来（转移）？③ 最开始的格子填什么（边界）？——"一问含义、二问转移、三问边界"，本课全部围绕这"三问"展开。
左边是暴力递归的"重复思考"（fib(3) 被算了两次，红的就是重复的）；右边是 DP 的"填表"（每格只算一次，后面的格直接抄前面的格）。
f(1)=1，f(2)=1，f(n)=f(n-1)+f(n-2)。写法一：裸递归——照定义写，简洁但慢（重复算）：
int fib(int n) {
if (n <= 2) return 1;
return fib(n - 1) + fib(n - 2); // 同一子题反复算
}
写法二：记忆化——算过的存进数组，下次直接"抄作业"（自顶向下）：
int memo[64] = {0};
int fib(int n) {
if (n <= 2) return 1;
if (memo[n]) return memo[n]; // 算过 → 抄作业
return memo[n] = fib(n - 1) + fib(n - 2);
}
写法三：自底向上填表——从小到大逐格填，一个数组搞定（本课主线）：
int fib(int n) {
int a = 1, b = 1; // f(1), f(2)：边界
for (int i = 3; i <= n; i++) {
int c = a + b; // 转移：f(i) = f(i-1) + f(i-2)
a = b; b = c;
}
return n <= 2 ? 1 : b;
}
做 DP 题就像填一张表，动手前先问三句：
三问答完，代码几乎是自动的：for 循环从小到大填表。如果转移里用到了还没算的格子——说明状态定义错了，回去重新问第一句。
题目：n 级台阶，每次跨 1 级或 2 级，问爬到顶的走法数。三问：状态 dp[i] = 爬到第 i 级的方案数；转移 dp[i] = dp[i-1] + dp[i-2]（最后一步跨 1 级或跨 2 级，两类走法互不重叠、合起来是全部）；边界 dp[1] = 1，dp[2] = 2。填表（n=10）：
i : 1 2 3 4 5 6 7 8 9 10 dp[i]: 1 2 3 5 8 13 21 34 55 89
验证小 n：n=3 时，dp[3] = dp[2] + dp[1] = 3，枚举核对：1+1+1、1+2、2+1，正好 3 种 ✓。n=4：dp[4] = 5，枚举：1111、112、121、211、22，正好 5 种 ✓。小例子数得过来，就敢信大例子。
题目：一排 6 家，钱分别是 3、4、2、7、9、1 元，相邻两家不能同时偷，最多偷多少？三问：状态 dp[i] = 只看前 i 家时能偷到的最大金额；转移：第 i 家不偷 → 金额 = dp[i-1]；偷 → 第 i-1 家必须空着，金额 = dp[i-2] + w[i]；两情况取大：dp[i] = max(dp[i-1], dp[i-2] + w[i])；边界：dp[0] = 0，dp[1] = w[1] = 3。填表：
家 i : 0 1 2 3 4 5 6 钱 w : 3 4 2 7 9 1 dp[i]: 0 3 4 5 11 14 14
读表：dp[4] = max(5, 4+7) = 11（偷 1、4 两家：3+7）；dp[5] = max(11, 5+9) = 14（偷 1、3、5 家：3+2+9）；dp[6] = max(14, 11+1) = 14（第 6 家钱太少，不如不偷）。答案 14 元。注意这是 max 型转移（优化问题），和斐波那契/爬楼梯的求和型转移（计数问题）是 DP 的两大门派：计数相加，优化取大。
dp[i-1]，不要再加 w[i]（那等于偷了还说不偷）。② "偷"分支必须跳一家用 dp[i-2]，用 dp[i-1] 就可能和 i-1 家撞车。③ dp[0] = 0 别忘——它是"偷第 1 家"情况的地基。一维 DP 两道经典题：爬楼梯（求和型）+ 打家劫舍（max 型）。
// 一维 DP：爬楼梯 + 打家劫舍 #include <bits/stdc++.h> using namespace std; int main() { // 1) 爬楼梯：n 级台阶，每次 1 或 2 级，方案数 int n = 10; vector<int> f(n + 1); f[1] = 1; f[2] = 2; // 边界 for (int i = 3; i <= n; i++) f[i] = f[i - 1] + f[i - 2]; // 转移（求和型） printf("爬 n=%d 级: %d 种\n", n, f[n]); // 89 // 2) 打家劫舍：相邻不能同时偷，最大金额 int w[] = {0, 3, 4, 2, 7, 9, 1}; // 1 开始编号 int m = 6; vector<int> dp(m + 1, 0); dp[0] = 0; dp[1] = w[1]; // 边界 for (int i = 2; i <= m; i++) dp[i] = max(dp[i - 1], dp[i - 2] + w[i]); // 转移（max 型） printf("最多偷: %d 元\n", dp[m]); // 14（偷 1、3、5 家） return 0; }
n+1、从 1 编号，边界格先填再进 for。② 求和型 DP 数值增长快，n 大时可能爆 int（GESP5 学过高精度，这里先记住风险）。③ 抄转移方程前先写清"状态含义"——含义错，方程必错。