1 篇博文含有标签「动态规划」

字节面试题之猴子分香蕉

2022年2月4日 · 阅读需 7 分钟

最近几天在学习算法方面的知识,在动态规划这块,想起了去年面试字节时二面的算法题,当时因为水平有限没有在面试中做出来,今天又重新做了一下,有所收获,在此记录.(有关这道题在CSDN上的题解简直狗屁不通,垃圾堆里果然都是垃圾,当然这道题在谷歌上也没有较为官方的题解,请读者带着思考的方式看题解,勿全信,如有不对之处,请在评论区指正)
猴子分香蕉
题目
动物园有猴山，每天需要给猴子们发香蕉,猴子会排队依次取食。猴子们铺张浪费,会多拿食物,但最多不会拿超过自身食量的二倍且不会超过当前还存在的香蕉的一半,最后—个猴子除外(即最后—个猴子可以拿完剩余的所有香蕉)。

最少需要准备多少香蕉,能保证所有猴子都能吃饱?

输入输出

[4,3] -> 8
[4,3,5] -> 18
[4,3,5,7] -> 28

分析

先来理解题目意思,最少需要准备多少香蕉的隐含意思是不管前面的猴子怎么贪吃,多拿了不少香蕉,也要保证到最后一直猴子时,剩余的香蕉数量要满足猴子的食量,否则那最后一直猴子就会挨饿,不满足所有猴子都吃饱这一条件.理解这一点很重要.

从输入输出来倒推分析,以[4,3,5,7] -> 28这组数据为例. 取香蕉的策略是每只猴子都尽可能贪心多拿

首先28的一半为14,并且4*2为8,取小值8,因此第1只猴子取8,剩余20
20的一半为10,并且3*2为6,取小值6,因此第2只猴子取6,剩余14
14的一半为7,并且5*2为10,取小值7,因此第3只猴子取7,剩余7
到最后一直猴子,剩7给7,满足最后一只猴子的食量,猴子全部吃饱

假设准备的香蕉少于28,以27为例

首先27的一半为13.5,并且4*2为8,取小值8,因此第1只猴子取8,剩余19
19的一半为9,5,并且3*2为6,取小值6,因此第2只猴子取6,剩余13
13的一半为6.5,并且5*2为10,取小值6.5,因此第3只猴子取6.5,剩余6.5
到最后一直猴子,剩6.5给6.5, 6.5 < 7, 不满足最后一只猴子的食量,猴子无法全部吃饱

因此28确实是需要准备的最少香蕉数量

开始动态规划解题

首先定义状态,我们可以看到,不管那种情况,最后需要满足的条件都是最后一只猴子也要吃饱,也仅仅只需要吃饱,不需要多吃,因此预期上我们给最后一只猴子准备的香蕉数就是猴子本身的食量.由此可以看出这道题肯定是要倒着递推的.因此我们把dp[i]定义为要喂[i, ..., last]猴子需要的食物
根据题目给出的条件,推递推方程. dp[i]是[i, ..., last]猴子需要的食物, 那么dp[i+1]是[i+1, ..., last]猴子需要的食物第i只猴子分的香蕉数就是dp[i] - dp[i+1], 猴子数组我们定为monkey,那么可以得到下面不等式

dp[i] - dp[i+1] <= 2*monkey[i] // 不会拿超过自身食量的二倍
dp[i] - dp[i+1] <= dp[i] / 2 // 不会超过当前还存在的香蕉的一半
dp[i] - dp[i+1] >= monkey[i] // 每只猴子吃饱不饿
由2,3还可以推出 monkey[i]<= dp[i] / 2

整理得

dp[i] >= dp[i+1] + monkey[i]
dp[i] >= 2 * monkey[i]
dp[i] <= 2 * dp[i+1]
dp[i] <= dp[i+1] + 2 * monkey[i]

得递推公式

    dp[i] = Math.max(
      Math.min(2 * dp[i + 1], dp[i + 1] + 2 * monkey[i]),
      dp[i + 1] + monkey[i],
            monkey[i] * 2
    );

进一步分析,min当中的第二项其实已经保证了max第二项的肯定成立,因此max第二项其实是多余的,可以删去,最后得到递推公式

    dp[i] = Math.max(
      Math.min(2 * dp[i + 1], dp[i + 1] + 2 * monkey[i]),
            monkey[i] * 2
    );

最终代码

function giveBanana(monkey = []) {
  if (!monkey || !monkey.length) return 0;
  let dp = new Array(monkey.length).fill(0);
  dp[dp.length - 1] = monkey[dp.length - 1];
  for (let i = dp.length - 2; i >= 0; i--) {
    dp[i] = Math.max(
      Math.min(2 * dp[i + 1], dp[i + 1] + 2 * monkey[i]),
            monkey[i] * 2
    );
  }
  return dp[0];
}

console.log(giveBanana([4, 3])); // 8
console.log(giveBanana([4, 3, 5])); // 18
console.log(giveBanana([4, 3, 5, 7])); // 28

总结

本题的主要的三个注意点

倒着推
状态的定义
获得递推方程较难

希望对网上搜索这道题的小伙伴有所帮助.

猴子分香蕉​

题目​

分析​

总结​

猴子分香蕉

题目

分析

总结