动态规划—鸡蛋掉落问题

鸡蛋掉落问题是一个经典的动态规划问题。问题描述如下：有一栋高楼，给你两个鸡蛋。如果把鸡蛋从某一层扔下去，鸡蛋会摔碎，如果不摔碎，可以重复使用。现在问你：怎样用最少的尝试次数找出鸡蛋恰好摔碎的楼层？

假设我们有 $n$ 层楼，$k$ 个鸡蛋，我们要求的是最坏情况下最少需要的试验次数。

我们可以根据第一次扔鸡蛋的结果分为两种情况：

1. 鸡蛋碎了：这个时候我们只能从第一层开始逐个尝试。因此需要 $1+f(k-1,n-1)$ 次尝试，其中 $f(k-1,n-1)$ 表示剩下的 $k-1$ 个鸡蛋和 $n-1$ 层楼的情况下最坏情况下需要的尝试次数。

2. 鸡蛋没碎：这个时候我们需要在剩下的 $n-x$ 层楼中尝试。因此需要 $1+f(k,n-x)$ 次尝试，其中 $f(k,n-x)$ 表示剩下的 $k$ 个鸡蛋和剩下的 $n-x$ 层楼的情况下最坏情况下需要的尝试次数。

因此，我们可以得到状态转移方程：

$$f(k,n)=\min_{1\leq x\leq n}\{1+\max(f(k-1,n-1),f(k,n-x))\}$$

其中 $f(k,n)$ 表示 $k$ 个鸡蛋和 $n$ 层楼的情况下最坏情况下需要的尝试次数。

时间复杂度为 $O(kn^2)$。

相关问题

鸡蛋掉落问题状态转移方程

鸡蛋掉落问题是一个经典的动态规划问题，其状态转移方程为：

dp[i][j] = 1 + max(dp[i-1][k-1], dp[i][j-k])

其中，dp[i][j]表示i个鸡蛋，j层楼的最坏情况下最少需要扔多少次鸡蛋才能确定鸡蛋的硬度；k表示在第k层楼扔鸡蛋，分为两种情况：鸡蛋碎了，即从第k层往下一层开始继续测试，所以是dp[i-1][k-1]；鸡蛋没碎，即从第k层往上一层开始继续测试，所以是dp[i][j-k]。最后取两者的最大值再加上本次扔鸡蛋的次数1，即为最优解。

需要注意的是，这个状态转移方程需要通过循环来实现，而且需要考虑边界情况，即当i=0或j=0时，dp[i][j]=0。

鸡蛋掉落问题C++带阿米

以下是带有注释的鸡蛋掉落问题的 C++ 代码实现：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1005;

int n, k;
int dp[N][N];  // dp[i][j] 表示 i 个鸡蛋在 j 层楼最多可以尝试多少次

int main()
{
    cin >> n >> k;

    // 当只有一颗鸡蛋时，最多需要尝试 k 次
    for (int j = 1; j <= k; j ++ ) dp[1][j] = j;

    // 当只有一层楼时，最多只需要尝试一次
    for (int i = 1; i <= n; i ++ ) dp[i][1] = 1;

    // 递推公式
    for (int i = 2; i <= n; i ++ )
        for (int j = 2; j <= k; j ++ )
        {
            dp[i][j] = 0x3f3f3f3f;  // 初始化为一个很大的数
            for (int x = 1; x <= j; x ++ )
                // 在 x 层楼扔鸡蛋，有两种情况：
                // 1. 鸡蛋碎了，需要在 x 层以下的楼层继续寻找
                // 2. 鸡蛋没碎，需要在 x 层以上的楼层继续寻找
                // max(dp[i-1][x-1], dp[i][j-x]) 表示这两种情况的最大值
                // 因为我们需要找到最坏情况下的最少尝试次数
                // 加 1 是因为我们需要在 x 层楼扔鸡蛋一次
                dp[i][j] = min(dp[i][j], max(dp[i-1][x-1], dp[i][j-x]) + 1);
        }

    // 输出 n 个鸡蛋在 k 层楼最少需要尝试的次数
    cout << dp[n][k] << endl;

    return 0;
}