鸡蛋的硬度

wflengxuenong · 2023-12-01 09:26:18 · 个人记录

鸡蛋的硬度

题目描述

给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。

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

每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。

请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？

算法分析

状态：很明显，就是当前拥有的鸡蛋数 K 和需要测试的楼层数 N。随着测试的进行，鸡蛋个数可能减少，楼层的搜索范围会减小，这就是状态的变化。

选择：其实就是去选择哪层楼扔鸡蛋。回顾刚才的线性扫描和二分思路，二分查找每次选择到楼层区间的中间去扔鸡蛋，而线性扫描选择一层层向上测试。不同的选择会造成状态的转移。

现在明确了「状态」和「选择」，动态规划的基本思路就形成了：肯定是个二维的 dp 数组或者带有两个状态参数的 dp 函数来表示状态转移；外加一个 for 循环来遍历所有选择，择最优的选择更新状态。

定义dp函数：dp(K, N)表示当有K个鸡蛋面对N层楼时，至少需要dp(K, N)次操作才能得到答案

状态转移：

如果鸡蛋碎了，那么鸡蛋的个数 K 应该减一，搜索的楼层区间应该从 [1..N] 变为 [1..i-1] 共 i-1 层楼；

如果鸡蛋没碎，那么鸡蛋的个数 K 不变，搜索的楼层区间应该从 [1..N] 变为 [i+1..N] 共 N-i 层楼。

所以算法的总时间复杂度是 O(K*N^2), 空间复杂度 O(KN)。

优化1：二分查找

首先简述一下原始动态规划的思路：

1、暴力穷举尝试在所有楼层 1 <= i <= N 扔鸡蛋，每次选择尝试次数最少的那一层；

2、每次扔鸡蛋有两种可能，要么碎，要么没碎；

3、如果鸡蛋碎了，F 应该在第 i 层下面，否则，F 应该在第 i 层上面；

4、鸡蛋是碎了还是没碎，取决于哪种情况下尝试次数更多，因为我们想求的是最坏情况下的结果。

核心的状态转移方程：

如果能够理解这个状态转移方程，那么就很容易理解二分查找的优化思路。

首先我们根据 dp(K, N) 数组的定义（有 K 个鸡蛋面对 N 层楼，最少需要扔几次），很容易知道 K 固定时，这个函数随着 N 的增加一定是单调递增的，无论你策略多聪明，楼层增加测试次数一定要增加。

那么注意 dp(K - 1, i - 1) 和 dp(K, N - i) 这两个函数，其中 i 是从 1 到 N 单增的，如果我们固定 K 和 N，把这两个函数看做关于 i 的函数，前者随着 i 的增加应该也是单调递增的，而后者随着 i 的增加应该是单调递减的：

优化2 决策单调性

方法二涉及决策单调性，是竞赛中的考点。这里我们不会叙述 何为决策单调性 以及 如何根据决策单调性写出优化的动态规划，而是仅指出决策单调性的存在性。

思路

我们重新写下方法一中的状态转移方程

作者：力扣官方题解 链接：https://leetcode.cn/problems/super-egg-drop/solutions/197163/ji-dan-diao-luo-by-leetcode-solution-2/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

#include<iostream>
#include<string.h>
using namespace std;
int f[209][209],st[209][209];
const int inf=0x3f3f3f3f;
int work(int n,int m) {
    for(int i=1; i<=n; i++)f[i][1]=i,st[i][1]=i-1,st[1][i]=1,f[1][i]=1;
    for(int j=2; j<=m; j++) {
        int k=1;//每次的决策点从1层楼开始，随着鸡蛋的数增加，决策楼层数间隔增加。
            for(int i=2; i<=n; i++) {
                f[i][j]=inf;
                if(f[i-k][j]>f[k-1][j-1])k++;
                    f[i][j]=min(f[i][j],f[k-1][j-1]+1);
            }

    }
    return f[n][m];
}
int main() {
    int n,m;
    while(cin>>n>>m) {
        f[0][0]=0;
        for(int i=1; i<=n; i++)f[i][1]=i,f[1][i]=1,f[0][i]=0;
        cout<<work(n,m)<<endl;
    }

}

方法四，状态重定义

题目不是给你 K 鸡蛋，N 层楼，让你求最坏情况下最少的测试次数 m 吗？ while 循环结束的条件是 dp[K][m] == N， 也就是给你 K 个鸡蛋，测试 m 次，正在进行第m次测试。 最坏情况下最多能测试 N 层楼。

 1 2 3             (4)             5 6 7 8

dp(k-1,m-1)       在这儿扔1次      dp(k,m-1) 测试

可以测试出的最多楼层数 可以测试出的最多楼层数

1、无论你在哪层楼扔鸡蛋，鸡蛋只可能摔碎或者没摔碎，碎了的话就测楼下，没碎的话就测楼上。

2、无论你上楼还是下楼，总的楼层数 = 楼上的楼层数 + 楼下的楼层数 + 1（当前这层楼）。

根据这个特点，可以写出下面的状态转移方程：