概念

学习使用递推的前提：一维数组，或者要会使用有限个变量，互相传递数值迭代前进的操作。

引言：一个实际问题的各种可能情况构成的集合，通常称为 “状态空间”，而程序的运行则是对状态空间的遍历。

递推 是程序遍历状态空间的基本方式。由已知的 “问题边界” 为起点，向 “原问题” 正向推导的扩展方式就是递推。

例子：询问有几个苹果，有每个人向上反馈，得到有n个苹果。

例子：Fibonacci数列

例子：兔子繁殖问题，把雌雄各一的一对新兔子放入养殖场中。每只雌兔在出生两个月以后，每月产雌雄各一的一对新兔子。试问，第n个月后养殖场中有多少对兔子。

  • 请编程实现一下，兔子繁殖问题，输出前10个月兔子的数量，每行一个数字
  • 理解兔子繁殖问题的时候，不建议画很繁杂的图，会容易扰乱思考
  • 集合划分方法，分析出递推公式，上个月就有的老兔子 + 这个月出生的新兔子f(n) = f(n - 1) + f(n - 2)

入门题目

上台阶
  1. //简单

菲波那契数列(2)
  1. //简单

Pell数列
  1. //简单

《一本通》题目

【例3.4】昆虫繁殖
  1. //用一个数组维护成虫数量，用一个数组维护卵的数量
  2. //不开long long见祖宗

【例3.5】位数问题
  1. //从1位数字开始递推，`f[i][0] 表示i位数字，有奇数个3的数字个数；同理，f[i][1]`

【例3.6】过河卒(Noip2002)
  1. //先做1194：移动路线
  2. //马的八个方向的枚举，check()的操作方法（每次进行一次check，判断9次；或者初始化的时候，设置好非法的点，后面递推的时候，避开非法的点），要注意LL

菲波那契数列(2)
  1. //

Pell数列
  1. //

上台阶
  1. //

流感传染
  1. //模拟，一层一层的扩大感染的范围
  2. //注意这个扩散是一层一层的扩散，要注意控制这个一层一层的问题，需要用到标记数组

放苹果
  1. //这个理解有难度，分为
  2. //盘子比苹果多的情况，苹果比盘子多的情况
  4. // 苹果的数量比盘子多的时候：
  5. // 有空盘子，那至少应该有一个盘子剩余：f(m,n-1)
  6. // 没有空盘子，那至少每一个盘子都有一个苹果，去掉n个苹果也是多放法总数不构成影响：f(m-n,n)
  7. // 盘子的数量比苹果的时候：
  8. // 去掉多余的盘子对摆放不构成影响：f(m, m)
  10. // 问题边界
  11. // 手里有0个苹果，就1种放法。（如果手里有1个苹果，这个方法并不唯一，如果面临现有盘子里苹果数量不一样）
  12. // 有1个盘子时候，也只有1种放法，就是有苹果就放这个盘子，没苹果就不放

吃糖果
  1. //打表找规律，然后就了了了

移动路线
  1. //和过河卒题目类似

判断整除
  1. //这道题放在后面做，和《1299：糖果》dp问题类似，和 knapsack problems 判断方案是否可行也类似
  2. //设计问题状态，dp[1...n][0....k-1],表示前i个数，%k余数是0... k-1的可能性
  3. //第 i 个数可能是前 i-1 个数基础上 +a[i] , 也可能是 -a[i]

踩方格
  1. //这道题目，开始锻炼，当前状态是从什么状态转过来的思维方式
  2. //画图理解第一步有三个方向可以走，构成了三个子问题。这三个子问题的特点，和第一步的特点进行对比
  3. //然后再往下走一步看看
  4. //每一步，要么有三个方向选择，要么有两个方向选择

山区建小学
  1. //区间dp，这道题目放在后面做
  2. //int dp[N][N]; //前i个村庄，建立j的小学的最小距离之和
  3. //需要预处理 [i, j] 之间建立一个学校的最小代价

更进一步

五种典型的递归关系：Fibonacci数列，Hanoi塔问题，平面分割问题，Catalan数，第二类Sitring数。这些问题需要初赛前学会。