算法知识

国王与金矿问题

问题描述：

国王有 10 座金矿，已知每座金矿的金币数量和所需开挖的人数，国王招募了 7 个人，问怎样合理分配才使挖去的金币数最多

问题补充：

• 每座金矿需要的人数固定，多一个，少一个都不行；
• 每座金矿要么全部挖出，要么不挖；
• 每个人只能挖一座金矿，不可重复挖；

分析

• 首先将金矿按 0，1，2，3，4，5，6，7，8，9 顺序进行编号；
• 首先我们先来到第 9 号金矿，9 号金矿存在 2 中情况，要么开挖，要么不挖；
• 设想，如果我知道 0 到 8 号金矿最多能开挖到的金币数(设为 y)：
  • 9 号开挖的情况：最大金币数 = y + 9 号金矿金币数
  • 9 号不开挖的情况：最大金币数 = y ，所以我只要取其 2 种情况中的最大值即可 Max(y + 9 号金矿金币数 , y )

g[i] 表示第 i 座金矿的金子数 p[i] 表示第 i 座金矿所需的人数 n 表示总的挖矿人数 f(n,i) 表示当有 n 个人时，挖取第 i 个金矿时所获取到的最多金币数

当 i == 0 （只有 1 座金矿）时：

• n >= p[i] ：总人数 >= 当前矿开挖所需的人数，最大金币数 = 当前矿的金币数 f(n,i) = g[i] ；
• n < p[i] ：总人数 < 当前矿开挖所需的人数，最大金币数 = 0 f(n, i) = 0 ;

当 i !== 0（有多座金矿）时：

• 如果当前矿开挖，最大金币数 = 前面矿的最大金币数 + 当前矿的金币数

  f(n,i) = f(n-p[i], i - 1) + g[i]

• 如果当前矿不开挖， 最大金币数 = 前面矿的最大金币数

  f(n,i-1)

所以 i !== 0 时， 最大金币数 = Max(f(n-p[i], i - 1) + g[i], f(n,i-1)) 两者中的最大值

爬台阶问题

问题描述:

一个人爬楼梯，每次只能爬 1 个台阶或 2 个台阶，如果有 n 个台阶，请问一共有多少种爬台阶的方法

问题分析

根据题目分析，每次只能爬 1 个台阶或 2 个台阶，那么起步的话，要么从 1 个台阶开始，要么从 2 个台阶开始， 这里将起步从 1 开始的方案称为 A方案 ,起步从 2 开始的方案称为 B 方案

那么走完 n 个台阶的方案就是：

N = A + B

现在所要解决的就是 A 和 B 分别是多少？下面通过一张表格来分析：

台阶数	A 方案	B 方案	N
0	0	0	0
1	1	0	1
2	1	1	2
3	2	1	3
4	3	2	5

• 当台阶为 0 时，A,B 2 种方案都是 0；
• 当台阶为 1 时，A = 1，B = 0；
• 当台阶为 3 时，A = [111,12] 2 种走法，B = [2] 1 种走法
• 当台阶为 4 时，A = [1111,1211,1122] 3 种走法， B = [211,22] 2 种走法

通过以上分析，我们可以发现 A = n - 1 , B = n - 2 ,由此我们可以推导出：

当 n > 2 时

f(n) = f(n - 1) + f(n - 2)

且 n <= 2 时

f(0) = 0 > f(1) = 1 > f(2) = 2

递归代码：

function f(n) {
  if (n === 0) return 0;
  if (n === 1) return 1;
  if (n === 2) return 2;
  return f(n - 1) + f(n - 2);
}

总结

通过以上分析，我们来总结一下如何写递归：

• 1.将大问题，分解为小问题，比如将 n 个台阶，分解为 1，2，3，4 个台阶
• 2.根据小问题的规律，通过规律递推出公式
• 3.通过公式的临界点，推导出递推的终止条件
• 4.将递推公式翻译成递归代码

这里我多细分了一部，将 1，2 两种走台阶的方法也细分了下，分为 A,B 两种方案，然后通过递推出 A，B 方案对应的公式，最后组合成最终的公式， 这样做是便于大家理解。