信奥赛CSP小学五年级动态规划入门

---

小学五年级动态规划入门

---

一、用生活例子引入动态规划

例子：存钱罐的秘密
小明有一个存钱罐，每天可以存1元或2元，他想知道存满5元有多少种不同的存法。

• 问题分解：
  • 存到1元：只有1种方法（每天存1元）。
  • 存到2元：2种方法（1+1 或 直接存2元）。
  • 存到3元：存到1元的方法数 + 存到2元的方法数 = 1 + 2 = 3种。
• 规律：当前问题的解 = 前面子问题的解之和。
• 动态规划的核心：记住每一步的结果，避免重复计算！

---

二、动态规划概念

• 动态规划（DP）：将大问题拆成小问题，通过解决小问题逐步解决大问题，并记录每个小问题的答案。
• 关键思想：
  1. 递推关系：当前答案如何由前面的答案推导出来。
  2. 记忆化存储：用数组或表格记录每一步的结果，避免重复计算。

---

三、从递推到动态规划的过渡

1. 递推算法举例：斐波那契数列

• 问题：求第n个斐波那契数（1, 1, 2, 3, 5, 8…）。
• 递推公式：f(n) = f(n-1) + f(n-2)，初始条件 f(1)=1, f(2)=1。
• 问题：直接递归会重复计算（如计算f(5)需要f(4)和f(3)，而f(4)又需要f(3)和f(2)）。

2. 动态规划优化：记忆化存储

• 用数组保存结果：计算过的值不再重复计算。
• 代码对比：

  // 递推（递归，低效）
  int fib(int n) {if (n == 1 || n == 2) return 1;return fib(n-1) + fib(n-2); // 重复计算
  }// 动态规划（高效）
  int dp[100] = {0};
  int fib_dp(int n) {if (n == 1 || n == 2) return 1;if (dp[n] != 0) return dp[n]; // 直接返回已计算的值dp[n] = fib_dp(n-1) + fib_dp(n-2);return dp[n];
  }
  

---

四、动态规划的步骤实现

以“爬楼梯”问题为例（每次爬1或2阶，到第n阶的方法数）：

1. 定义状态：dp[i]表示爬到第i阶的方法数。
2. 状态转移方程：dp[i] = dp[i-1] + dp[i-2]（从i-1阶爬1步，或从i-2阶爬2步）。
3. 初始条件：dp[1] = 1, dp[2] = 2。
4. 计算顺序：从小到大依次计算 dp[3], dp[4], ..., dp[n]。

---