POJ3783,leetcode887 扔鸡蛋

题目描述

你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N  共有 N 层楼的建筑。

每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。

你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。

每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。

你的目标是确切地知道 F 的值是多少。

无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少

样例

示例 1：

输入：K = 1, N = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。
否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。
如果它没碎，那么我们肯定知道 F = 2 。
因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。


示例 2：

输入：K = 2, N = 6
输出：3


示例 3：

输入：K = 3, N = 14
输出：4

数据范围

1 <= K <= 100
1 <= N <= 10000

解题思路

dp[i][j] 表示有j层楼， 剩余i个鸡蛋时， 最坏情况要确定f 所需的次数
(1)不破，  则排除掉了k层，剩余i-k层  则转化为 dp[i - k][j]
(2)破了 则剩余k- 1层， 球剩j - 1个   转化为 dp[k - 1][ j - 1]



根据动态规划的状态转移方程式和自底向上的求解思路，我们需要从1个鸡蛋1层楼的最优尝试次数，一步一步推导后续的状态，直到计算出3个鸡蛋4层楼的尝试次数为止。
首先，我们可以填充第一个鸡蛋在各个楼层的尝试次数，以及任意多鸡蛋在1层楼的尝试次数。
原因很简单：
1.只有一个鸡蛋，所以没有任何取巧方法，只能从1层扔到最后一层，尝试次数等于楼层数量。
2.只有一个楼层，无论有几个鸡蛋，也只有一种扔法，尝试次数只可能是1。

参考文献

CSDN博主「ITAK」: https://blog.csdn.net/qingshui23/article/details/52103660
B站 https://www.bilibili.com/video/av71050428?from=search&seid=12791911905768085937

代码实现

算法一:

时间复杂度

O(nmm)

#include<iostream>
using namespace std;

int f[110][10010];

int main(){
    int n,m;   //n个鸡蛋,m层楼

    cin>>n>>m;

    for(int i = 1 ; i <= n ; i++)
    {
        f[i][1] = 1;           //无论多少个鸡蛋,在只有一层楼的情况下最坏情况下的最少丢鸡蛋次数都为1
    }                           

    for(int i = 1 ; i <= m ; i++)
    {
        f[1][i] = i;            //无论多少层楼,在只有一个鸡蛋的情况下最坏情况下的最少丢鸡蛋次数都为i
                                //因为最坏情况下要把使用楼层都试一遍
    }

    for(int i = 2 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
            for(int k = 1 ; k < j ; k++)
                f[i][j] = min(f[i][j],max(f[i-1][k-1],f[i][j-k])+1);  //z最坏情况下的最小次数

    cout<<f[n][m]<<endl;                

    return 0;

}