题解 | #放苹果#
放苹果
https://www.nowcoder.com/practice/bfd8234bb5e84be0b493656e390bdebf
思路——将问题简化为有空盘子和没空盘子的情况，m个苹果，n个盘子
- 有空盘子：f(m, n)=f(m, n - 1)；
- 没有空盘子：就是每个盘子先放一个苹果，然后将剩下的m-n个苹果放在n个盘子上会有几种方法: f(m, n) = f(m - n, n), (m > n)；
如果苹果数m < 盘子数n,那就是将m个苹果放到m个盘子上会有几种方法: f(m, m)；
递归结束条件:当只有1个苹果或者0个苹果或者1个盘子的时候，只有1种方法： f(m, n) = 1, (m = 0, m = 1, n = 1);
综上所述，
- 当m > n时：f(m, n) = f(m, n - 1) + f(m - n, n)
- 当m <= n时：f(m, n) = f(m, m)
- 当m = 0 或 m=1 或 n=1时，f(m, n) = 1;
以下是本次算法的代码, 有不足请指正
function putApple(m, n) {
if (m === 0 || m === 1 || n === 1) return 1;
if (m < n) return putApple(m, m);
else return putApple(m, n - 1) + putApple(m - n, n);
}
投递字节跳动等公司9个岗位
查看30道真题和解析