🧗 简单动态规划

有些问题拆成小问题后，同一个小问题会被算很多遍。动态规划的办法是：把小问题的答案记在小本本上，下次直接翻本子，绝不重复劳动。爬楼梯、找零钱、装背包，都靠它变快。

考纲知识点：一维动态规划
简单背包

📖

考纲 · 知识点详述

摘自《CCF编程能力等级认证 C++&Python 认证标准》C++ 六级

(5)掌握简单动态规划的算法思想，能够使用代码解决相应的一维动态规划问题和简单背包问题。

📚

先学一学

花 6 分钟读完下面 5 课，再去闯关就不慌啦

🧠 动态规划：大问题拆小问题，小问题答案记下来

四年级学过递推：从已知的往前一步步推。六年级的动态规划（DP）是它的加强版，多了两个好习惯：

📒 好习惯 1：拆小问题（状态）

把大问题拆成一排小问题，每个小问题叫一个「状态」，比如「到第 i 级台阶有几种走法」。

💡 口诀：状态就是一个个小问题，问法要清楚。

📒 好习惯 2：记答案（记忆化）

同一个小问题算过一次就写进本子，下次直接抄答案。比如算斐波那契时 fib(3) 会被要很多次，记下来就不用一遍遍重算。

💡 口诀：算过就记，用到就翻；同样的题不重算第二遍。

🪜 爬楼梯：一维动态规划的招牌例子

小明上楼梯，一次可以跨 1 级或 2 级。问到第 n 级有几种走法？想一下最后一步：到第 n 级之前，小明一定站在第 n-1 级（再跨 1 级）或第 n-2 级（再跨 2 级）。所以：

🔢 递推式与初始值

到第 1 级有 1 种走法，到第 2 级有 2 种（1+1 或 2）；
到第 n 级的走法 = 到第 n-1 级的走法 + 到第 n-2 级的走法。
算一算：f[1]=1、f[2]=2、f[3]=3、f[4]=5、f[5]=8……和斐波那契是一家人。

💡 口诀：最后一步看两处——从 n-1 跨 1 级，或从 n-2 跨 2 级，两边加起来。

🧪 读代码：用数组从小往大推

看得懂就好，不用背：

int f[100];
f[1] = 1; f[2] = 2; // 初始值
for (int i = 3; i <= n; i++)
f[i] = f[i-1] + f[i-2]; // 从第 3 级一直推到第 n 级

从小到大填表，每个 f[i] 只算一次——这就是一维动态规划。

💡 口诀：定初值、写递推、从小到大把表填完。

🎒 简单背包：容量有限，塞进价值最高的东西

去野营只能背一个 5 kg 的书包，面前有好几件宝贝，每件有重量和价值：
A 帐篷 3kg 值 9 元，B 睡袋 2kg 值 6 元，C 水壶 2kg 值 5 元。
怎么选让总价值最高还不超重？ A+B = 5kg 值 15 元，A+C 也 5kg 但只值 14 元，B+C 才 4kg 值 11 元——所以选 A+B。

🧭 每一件都问自己：拿还是不拿？

对每件宝贝只有两种选择：不拿它，或拿它（拿它就得给它腾出重量）。比较两种情况哪个价值高，取大的那个。这种「每件最多拿一次」的背包叫 0/1 背包。

💡 口诀：每件宝贝二选一——不拿保持原样，拿了腾重量，价值高者胜。

⚠️ 为什么不能直接拿最贵的？

有时最贵的东西太重，塞了它别的都放不下，反而不如「两件轻的加起来」。所以背包题要把所有组合比一遍，这正是动态规划擅长的：用一张表记下「前几件宝贝、每种容量下最多值多少」，一格一格推。

💡 口诀：贪心看眼前，背包要比全；表格一格一格填，容量价值两手抓。

🧭 动态规划四步口诀

1️⃣定状态：把小问题问清楚，比如「到第 i 级有几种走法」。
2️⃣找转移：想清楚大问题怎么由小问题拼出来（递推式）。
3️⃣写初值：最小的那几个状态答案是什么，比如 f[1]=1、f[2]=2。
4️⃣按顺序推：从小到大把表填满，最后读答案。

🧱 生活类比：搭积木塔

先打最稳的地基（初值），再一块一块往上垒（递推），每一层都踩在下面一层上面（状态转移）。想盖到第 10 层，不用从第一层重新数，因为每一层都记着。

💡 口诀：状态、转移、初值、顺序——四步走，DP 不发愁。

🆚 易混对比：普通递归 vs 动态规划 vs 贪心

📊 三兄弟的差别

· 普通递归：大问题调小问题，但同一个小问题可能被反复算，越算越慢。
· 动态规划：递推 + 记忆化，算过的小问题存起来，不重算，稳又快。
· 贪心：每一步只挑眼前最好的，简单但不一定全局最好。

💡 口诀：递归爱重复劳动，DP 拿本子记账，贪心只看眼前不一定最优。

🪙 例子：找零钱 6 元，有 4 元和 3 元两种币

贪心会先拿最大的 4 元，剩下 2 元凑不出，只好放弃——其实正确答案是 3+3 两枚。这种时候贪心失灵，动态规划把「凑 0 元、凑 1 元……凑 6 元」全部记下来比较，就能找到最优解。

💡 口诀：贪心一时爽，DP 想得全；找零凑数别贪心，全部比过才最优。

🎯

闯关小锦囊 · 考点提醒

动态规划 = 拆小问题（状态）+ 递推关系 + 初始值 + 从小到大算。
核心好习惯是记忆化：算过的小问题存起来，绝不重复算。
一维 DP 招牌题：爬楼梯 f[i] = f[i-1] + f[i-2]，初值 f[1]=1、f[2]=2。
简单背包：容量有限选价值最高；每件宝贝拿或不拿比一比（0/1 背包）。
0/1 背包用一维数组时，内层容量要从大到小倒着走，否则同一件物品会被用好几次。
贪心只看眼前不一定最优（找零钱例子）；DP 把所有可能比一遍更可靠。

🎮

学完了？来闯关！

下面 16 个小挑战，点一点就能玩

Demo 原型 · 每个知识点独立页面 · 暂不含真实编译与进度存储。