知识点

LeetCode算法题

1. LeetCode算法题

   1. 高楼扔鸡蛋

      解题思路：

      如果不限制鸡蛋数量，使用二分查找就是最好的解决方法。

      但是，限制了鸡蛋数量，就不可以使用二分查找了。该题求最值，因此判断是否可以使用动态规划，结论是可以。

      使用动态规划，需要判断状态和选择。「状态」很明显，就是当前拥有的鸡蛋数K和需要测试的楼层数N。随着测试的进行，鸡蛋个数可能减少，楼层的搜索范围会减小，这就是状态的变化。「选择」其实就是去选择哪层楼扔鸡蛋

      明确了「状态」和「选择」，暴力穷举的思路就有了：用带两个参数的递归函数，函数中加一个 for 循环来遍历所有选择。

      利用dp数组来消除重叠子问题：使用二维dp数组来存储所有状态下，需要的鸡蛋数量，择最优的选择更新结果。

      我们在第i层楼扔了鸡蛋之后，可能出现两种情况：鸡蛋碎了，鸡蛋没碎。注意，这时候状态转移就来了：如果鸡蛋碎了，那么鸡蛋的个数K应该减一，搜索的楼层区间应该从[1..N]变为[1..i-1]共i-1层楼；如果鸡蛋没碎，那么鸡蛋的个数K不变，搜索的楼层区间应该从 [1..N]变为[i+1..N]共N-i层楼。

      因为我们要求的是最坏情况下扔鸡蛋的次数，所以鸡蛋在第i层楼碎没碎，取决于那种情况的结果更大。

      递归的 base case 很容易理解：当楼层数N等于 0 时，显然不需要扔鸡蛋；当鸡蛋数K为 1 时，显然只能线性扫描所有楼层，