区间动态规划-扔鸡蛋

OJ平台：T1300

题目：
你面前有一栋从 1 到 N 共 N 层的楼，然后给你 K 个鸡蛋（K 至少为 1）。现在确定这栋楼存在楼层 0 <= F <= N，在这层楼将鸡蛋扔下去，鸡蛋恰好没摔碎（高于 F 的楼层都会碎，低于 F 的楼层都不会碎）。现在问你，最坏情况下，你至少要扔几次鸡蛋，才能确定这个楼层 F 呢？
鸡蛋没有撞碎可以重复用，每个鸡蛋的抗摔能力一样，鸡蛋可以有剩余。

如果没有鸡蛋个数限制，二分思路显然可以得到最少尝试的次数。
使用二分查找思路，我先去第 (1 + 10) / 2 = 5层扔一下：如果碎了说明 F 小于 4，我就去第 (1 + 4) / 2 = 2 层试……
如果没碎说明 F 大于等于 4，我就去第 (5 + 10) / 2 = 7 层试……

现在给你了鸡蛋个数的限制 K(k<$\log_{2}n$)，直接使用二分思路就不行了。

比如说只给你 1 个鸡蛋，10层楼，你敢用二分吗？你直接去第 5层扔一下，如果鸡蛋没碎还好，但如果碎了你就没有鸡蛋继续测试了，无法确定鸡蛋恰好摔不碎的楼层 F 了。这种情况下只能用线性扫描的方法，算法返回结果应该是 10。

如果先用二分查找，等到只剩 1 个鸡蛋的时候再执行线性扫描，这样得到的结果是不是就是最少的扔鸡蛋次数呢？
结果并不是，比如说把楼层变高一些，100 层，给你 2 个鸡蛋，你在 50 层扔一下，碎了，那就只能线性扫描 1～49 层了，最坏情况下要扔 50 次。
如果不要「二分」，变成「五分」「十分」都会大幅减少最坏情况下的尝试次数。比方说第一个鸡蛋每隔十层楼扔，在哪里碎了第二个鸡蛋一个个线性扫描，总共不会超过 20 次。最优解其实是 14 次。

假设 f(k, m) 表示用 k 个鸡蛋，尝试 m 次，最多能测出的楼层数。

我们的目标是：找到最小的 m，使得 f(k, m)>=n。

递推逻辑

当你扔下一个鸡蛋时，只有两种结果：

鸡蛋碎了：你还剩下k-1 个鸡蛋和 m-1 次机会，向下可以覆盖 f(k-1, m-1) 层。
鸡蛋没碎：你还剩下 k 个鸡蛋和 m-1 次机会，向上可以覆盖 f(k, m-1) 层。
加上当前层：你自己站的那一层也算 1 层。

因此，递推公式为：f(k, m) = f(k-1, m-1) + f(k, m-1) + 1

2. 最优解算法实现 (C++)

我们可以使用一个二维数组 dp[k][m] 来存储结果。

#include <iostream>
#include <vector>

int solve(int n, int k) {
    // dp[i][j] 表示有 i 个鸡蛋，尝试 j 次，最多能测多少层
    // 因为尝试次数不会超过楼层数 n，所以列大小设为 n+1
    std::vector<std::vector<int>> dp(k + 1, std::vector<int>(n + 1, 0));
    
    int m = 0; // 尝试次数
    while (dp[k][m] < n) {
        m++;
        for (int i = 1; i <= k; ++i) {
            // 公式：碎了能测到的 + 没碎能测到的 + 当前层
            dp[i][m] = dp[i - 1][m - 1] + dp[i][m - 1] + 1;
        }
    }
    return m;
}

int main() {
    int n, k;
    std::cout << "输入楼层 n 和鸡蛋数 k: ";
    std::cin >> n >> k;
    std::cout << "最优策略下最多需要尝试 " << solve(n, k) << " 次" << std::endl;
    return 0;
}

3. 策略对比

为了让你直观感受“资源（鸡蛋）”对“效率（尝试次数）”的影响，以 100 层楼 为例：

鸡蛋个数 (k)	最多尝试次数 (m)	策略类型
1 个	100 次	极其保守（线性扫描）
2 个	14 次	数学优化
3 个	9 次	更加激进的分段
7 个	7 次	二分查找 ($2^7 = 128 > 100$)

规律：当鸡蛋足够多（$k \geq \log_2 n$）时，最优解就是二分查找。但在资源有限（鸡蛋少）时，必须采用上述动态规划的策略。

一、两个鸡蛋的最优策略

2025年CSP-S阅读程序-2

思路： 先找最小的 w，使得 w*(w+1)/2 >= n。

第一个鸡蛋按 递减步长 跳跃：第 w 层、第 w+(w-1) 层、第 w+(w-1)+(w-2) 层……

跳跃序列: w, w+(w-1), w+(w-1)+(w-2), ...
步长依次: w, w-1, w-2, ...

关键设计： 每跳一次，剩余步长就减 1。当第一个蛋在某区间碎了，第二个蛋在该区间线性扫描的步数恰好等于剩余步长，两段加起来始终 ≤ w 次。

举例（n=100）：

w=14，因为 14+13+12+11+10+9+8+7+6+5+4+1=100
第一蛋跳：14 → 27 → 39→ 50……..
若在 69 碎了，第二蛋扫 51、52…，最多再用 14 次
总次数始终 ≤ 14 次

最坏情况次数是 O(√n)，

二、递归方法 (f 函数)

代码讲解：

int f(int n, int m) {
    if (m == 1) return n;  // 只有一个鸡蛋，只能线性搜索
    if (n == 0) return 0;  // 没有楼层，不需要扔
    int ret = INT_MAX;
    for (int i = 1; i <= n; i++)
        ret = min(ret, max(f(n - i, m), f(i - 1, m - 1)) + 1);
    return ret;
}

思路：对于每一层楼 i，我们有两种情况：
1. 鸡蛋碎了，那么我们需要在 i-1 层楼和 m-1 个鸡蛋中继续搜索。
2. 鸡蛋没碎，那么我们需要在 n-i 层楼和 m 个鸡蛋中继续搜索。
时间复杂度：由于递归树的高度为 n，每次递归调用有 n 种选择，时间复杂度为 O(n^m)，非常高。
缺点：重复计算非常多，效率低下。

三、带记忆化的递归方法 (f1 函数)

int f1(int n, int m) {
    if (m == 1) return n;
    if (n == 0) return 0;
    if (memo[n][m] != -1) return memo[n][m];

    int ret = INT_MAX;
    for (int i = 1; i <= n; i++)
        ret = min(ret, max(f1(n - i, m), f1(i - 1, m - 1)) + 1);
    return memo[n][m] = ret;
}

思路：与递归方法相同，但使用了记忆化技术来避免重复计算。
时间复杂度：由于记忆化避免了重复计算，时间复杂度降低到 O(n^2 * m)。
优点：相比纯递归方法，效率大幅提升。

3. 递推方法（动态规划） (g 函数)

int g(int n,int m){
    h.assign(n+1,vector<int>(m+1,INT_MAX));
    for (int i =1; i <=n; i++)
        h[i][1]=i;
    for (int j =1; j <=m; j++)
        h[0][j]=0;
    
    for (int i = 1; i <=n; i++){
        for (int j =2; j <=m; j++){
            for(int k=1;k<=i;k++)
                h[i][j]=min(h[i][j],max(h[i-k][j],h[k-1][j-1])+1);
        }
    }
    return h[n][m];
}

思路：使用动态规划表 h[i][j] 来存储 i 层楼和 j 个鸡蛋时的最小尝试次数。通过三重循环填充这个表。
时间复杂度：O(n^2 * m)，与带记忆化的递归方法相同，但避免了递归的开销。

二分搜索优化的递归方法 (b 函数)

int b(int n, int m) {
    if (n == 0) return 0;  // 没有楼层，不需要扔
    if (m == 1) return n;  // 只有一个鸡蛋，需要线性遍历
    if (memo[n][m] != -1) return memo[n][m];

    int left = 1, right = n, res = INT_MAX;
    while (left <= right) {
        int mid = (left + right) / 2;
        int break_case = b(mid - 1, m - 1); // 鸡蛋碎了，搜索下方
        int no_break_case = b(n - mid, m);  // 鸡蛋没碎，搜索上方
        int res=min(res, max(break_case, no_break_case) + 1); // 取最坏情况

        if (break_case > no_break_case) {
            right = mid - 1; // 碎了，往下找 
        } else {
            left = mid + 1;  // 没碎，往上找
        }
    }
    
    return memo[n][m] = res;
}

思路：通过二分搜索来优化递归过程，减少搜索空间。每次选择中间楼层 mid，根据鸡蛋是否碎来决定继续搜索上方还是下方。
时间复杂度：由于二分搜索的引入，时间复杂度降低到 O(n * m * log n)。

代码实现：

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2025-02-03 09:41:28
 * 最后修改: 2025-02-03 22:59:57
 * 文件描述: 扔鸡蛋问题  egg dropping
****************************************************************/
#include <algorithm>
#include <climits>
#include <iostream>
#include <limits>
#include <vector>
using namespace std;


vector<vector<int> > h;
vector<vector<int> > memo;
//递归方法
int f(int n, int m){
    if(m==1)return n;
    if(n==0)return 0;

    int ret=INT_MAX;
    for (int i =1; i <=n; i++)
       ret=min(ret,max(f(n-i,m),f(i-1,m-1))+1);
    return ret;        
    }


// 递归方法（带记忆化）
int f1(int n, int m) {

    if (m == 1) return n;
    if (n == 0) return 0;
    if (memo[n][m] != -1) return memo[n][m];

    int ret = INT_MAX;
    for (int i = 1; i <= n; i++)
        ret = min(ret, max(f1(n - i, m), f1(i - 1, m - 1)) + 1);
    return memo[n][m] = ret;
}

//递推方法
int g(int n,int m){
    h.assign(n+1,vector<int>(m+1,INT_MAX));
    for (int i =1; i <=n; i++)
        h[i][1]=i;
    for (int j =1; j <=m; j++)
        h[0][j]=0;
    
    for (int i = 1; i <=n; i++){
        for (int j =2; j <=m; j++){
            for(int k=1;k<=i;k++)
                h[i][j]=min(h[i][j],max(h[i-k][j],h[k-1][j-1])+1);
        }
    }
    return h[n][m];
}

int b(int n, int m) {
    if (n == 0) return 0;  // 没有楼层，不需要扔
    if (m == 1) return n;  // 只有一个鸡蛋，需要线性遍历
    if (memo[n][m] != -1) return memo[n][m];

    int left = 1, right = n, res = INT_MAX;
    while (left <= right) {
        int mid = (left + right) / 2;
        int break_case = b(mid - 1, m - 1); // 鸡蛋碎了，搜索下方
        int no_break_case = b(n - mid, m);  // 鸡蛋没碎，搜索上方
        int res=min(res, max(break_case, no_break_case) + 1); // 取最坏情况
       
        if (break_case > no_break_case) {
            right = mid - 1; // 碎了，往下找 
        } else {
            left = mid + 1;  // 没碎，往上找
        }
    }
    
    return memo[n][m] = res;
}

int main(){
    int n,m;// n为楼层，n为鸡蛋个数
    cin>>n>>m;
    memo.assign(n + 1, vector<int>(m + 1, -1));
//  cout<<f(n,m)<<endl;
    cout<<f1(n,m)<<endl;
    memo.assign(n + 1, vector<int>(m + 1, -1));
    cout<<g(n,m)<<endl;
    memo.assign(n + 1, vector<int>(m + 1, -1));
    cout<<b(n, m);
    return 0;
}

为什么第四种方法比第三种更优：

第四种方法（b 函数）是一种二分搜索优化的动态规划方法，它通过结合二分搜索的思想，显著减少了动态规划中的计算量，从而比第三种方法（普通的动态规划）更高效。下面我们结合代码详细讲解为什么这种方法更优。

第四种方法的代码

int b(int n, int m) {
    if (n == 0) return 0;  // 没有楼层，不需要扔
    if (m == 1) return n;  // 只有一个鸡蛋，需要线性遍历
    if (memo[n][m] != -1) return memo[n][m];

    int left = 1, right = n, res = INT_MAX;
    while (left <= right) {
        int mid = (left + right) / 2;
        int break_case = b(mid - 1, m - 1); // 鸡蛋碎了，搜索下方
        int no_break_case = b(n - mid, m);  // 鸡蛋没碎，搜索上方
        int worst_case = max(break_case, no_break_case) + 1; // 取最坏情况
        res = min(res, worst_case);

        if (break_case > no_break_case) {
            right = mid - 1; // 碎了，往下找 
        } else {
            left = mid + 1;  // 没碎，往上找
        }
    }

    return memo[n][m] = res;
}

核心思想

在第三种方法中，我们通过三重循环枚举所有可能的楼层 k（从 1 到 n），计算 h[i][j] 的值。然而，这种方法的时间复杂度较高（(O(n^2 \cdot m))）。

第四种方法通过二分搜索优化了寻找最佳楼层 k 的过程。具体来说：

单调性：对于固定的 n 和 m，break_case（鸡蛋碎了的情况）和 no_break_case（鸡蛋没碎的情况）之间存在单调性：

随着 k 的增加，break_case 的值会增加（因为需要搜索的楼层数增加）。
随着 k 的增加，no_break_case 的值会减少（因为需要搜索的楼层数减少）。

最优解的位置：最优解位于 break_case 和 no_break_case 的交点附近。通过二分搜索，我们可以快速找到这个交点，从而减少计算量。

代码详细解析

1. 边界条件

if (n == 0) return 0;：如果没有楼层，不需要扔鸡蛋。
if (m == 1) return n;：如果只有一个鸡蛋，只能线性搜索，最坏情况下需要扔 n 次。

2. 记忆化检查

if (memo[n][m] != -1) return memo[n][m];：如果当前状态已经计算过，直接返回结果，避免重复计算。

3. 二分搜索

初始化：
left = 1：搜索的起始楼层。
right = n：搜索的结束楼层。
res = INT_MAX：用于存储最小尝试次数。
二分搜索过程：
计算中间楼层 mid = (left + right) / 2。
分别计算 break_case（鸡蛋碎了的情况）和 no_break_case（鸡蛋没碎的情况）：
- break_case = b(mid - 1, m - 1)：在 mid-1 层楼和 m-1 个鸡蛋的情况下继续搜索。
- no_break_case = b(n - mid, m)：在 n-mid 层楼和 m 个鸡蛋的情况下继续搜索。
计算当前的最坏情况：worst_case = max(break_case, no_break_case) + 1。
更新最小值：res = min(res, worst_case)。
根据 break_case 和 no_break_case 的大小关系调整搜索范围：
- 如果 break_case > no_break_case，说明最优解在左侧，调整 right = mid - 1。
- 否则，说明最优解在右侧，调整 left = mid + 1。

4. 返回结果

将结果存储到 memo[n][m] 中并返回。

为什么比第三种方法更优？

1. 时间复杂度

第三种方法：三重循环，时间复杂度为 (O(n^2 *m))。
第四种方法：通过二分搜索将内层循环的复杂度从 (O(n)) 降低到 (O(\log n))，因此总时间复杂度为 (O(n \cdot m \cdot \log n))。

2. 减少计算量

第三种方法需要枚举所有可能的楼层 k（从 1 到 n），而第四种方法通过二分搜索快速定位最优解，避免了大量不必要的计算。

3. 空间复杂度

两种方法的空间复杂度相同，均为 (O(n \cdot m))，用于存储记忆化表。

举例说明

假设 n = 100，m = 2：

第三种方法：需要计算 (100¹⁰⁰ = 10,000) 次状态转移。
第四种方法：通过二分搜索，每次搜索范围减半，最多需要计算 (100*log_2( 100) \approx 700) 次状态转移。

显然，第四种方法在大规模问题中具有显著优势。

总结

第四种方法通过结合二分搜索和动态规划，显著减少了计算量，时间复杂度从 (O(n^2 \cdot m)) 降低到 (O(n \cdot m \cdot \log n))。这种优化在大规模问题中尤为有效，是解决扔鸡蛋问题的推荐方法。

Previous Topic

Back to Lesson

Next Topic