概念

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

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

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

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

例子：Fibonacci数列

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

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

入门题目

上台阶

  1. //简单

菲波那契数列(2)

  1. //简单

Pell数列

  1. //简单

练习题目

例题，【例3.4】昆虫繁殖

  1. //用一个数组维护成虫数量，用一个数组维护卵的数量
  2. //不开long long见祖宗

例题，流感传染

  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种放法，就是有苹果就放这个盘子，没苹果就不放

ybt上练习请注意，【例3.5】位数问题，判断整除，踩方格，山区建小学，先不做，学一段时间再回来做