用已经算好的小问题，推出更大的问题
这一课只练一件事：用已经算好的小问题推出更大的问题，这叫 （C++ 里常用数组 dp）。必会：用一句话解释 dp[i]、写出 、用手算前三步验证 。最小示例：每次走 1 或 2 级台阶，求走到第 n 级的方法数。边界是忘了初值，以及 n=1。建议掌握：把答案记在 表里。填 n 格大约 O(n)，常见测试点能通过。状态压缩、二维背包、树形 DP 是拓展。这里不会在浏览器里运行 C++。
任务 1：先选出动态规划是什么、dp[i] 表示什么
用已经算好的小问题推出更大的问题。爬楼梯里， dp[i] 表示走到第 i 级的方法数。点不认识的词可看基础解释。
必会：能用一句话说清 dp[i]。这里不会在浏览器里运行 C++，只练习选择和走过程。
动态规划在本课是什么意思？小问题推大问题 · 必会
爬楼梯里 dp[i] 表示什么？状态含义 · 必会
任务 2：按顺序手算爬楼梯前三步
最小示例：每次走 1 或 2 级，求走到第 3 级的方法数。按顺序点三步：先写 dp[1] = 1，再写 dp[2] = 2，最后用 dp[3] = dp[2] + dp[1] = 3。这里不会在浏览器里运行 C++。
必会：能解释每一步为什么这样填。边界：不要跳过初值。填 n 格大约 O(n)，常见测试点能通过。
- int dp[4];
- dp[1] = 1;
- dp[2] = 2;
- dp[3] = dp[2] + dp[1];
三步走完了，现在亲手把转移那一行敲出来：第 i 级只能从 i - 1 走 1 级上来，或者从 i - 2 一次走 2 级上来，两类走法都要 过来。下面是只读脚手架，只留一空给你敲键盘。
- int dp[50];
- dp[1] = 1; dp[2] = 2; // 初值必须先写
- for (int i = 3; i <= n; i++) {
- ; // 由前两级推出来
- }
- cout << dp[n];
dp[i] = dp[i - 1] + dp[i - 2]; // i=3 时就是 dp[3] = dp[2] + dp[1] = 3
任务 3：核对初值，并认出忘写初值会错
建议掌握：把答案记在 表里。现在 dp[1] = 1、dp[2] = 2、dp[3] = 3。如果忘了初值，转移会从空格子开始。n=1 时答案就是 dp[1] = 1。状态压缩、二维背包、树形 DP 是拓展。
必会 / 建议掌握 / 拓展：必会是解释 dp[i]、写出初值、手算前三步。建议掌握是一维 DP 表。状态压缩、二维背包、树形 DP 是拓展，现在不用当硬门槛。
- // 初值：dp[1] = 1，dp[2] = 2
- // 正确：dp[3] = 2 + 1 = 3
- // 错误：忘了初值就无法转移
- // 状态压缩、二维背包、树形 DP 是拓展
先选出为什么必须写初值：
再选出 n=1 和拓展边界：
任务 4：随机小测，看看你是否真的懂了
每次从本课题库抽出三道不同的选择题。题目与解析已通过校验，答完后看解析，不要只看分数；拿不准就回到对应任务再看一遍。