区间动态规划-扔鸡蛋

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，直接使用二分思路就不行了。

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

有的读者也许会有这种想法：二分查找排除楼层的速度无疑是最快的，那干脆先用二分查找，等到只剩 1 个鸡蛋的时候再执行线性扫描，这样得到的结果是不是就是最少的扔鸡蛋次数呢？

很遗憾，并不是，比如说把楼层变高一些，100 层，给你 2 个鸡蛋，你在 50 层扔一下，碎了，那就只能线性扫描 1～49 层了，最坏情况下要扔 50 次。
如果不要「二分」，变成「五分」「十分」都会大幅减少最坏情况下的尝试次数。比方说第一个鸡蛋每隔十层楼扔，在哪里碎了第二个鸡蛋一个个线性扫描，总共不会超过 20 次。
最优解其实是 14 次。最优策略非常多，而且并没有什么规律可言。

代码讲解：

1. 递归方法 (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)，非常高。
缺点：重复计算非常多，效率低下。

2. 带记忆化的递归方法 (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 \cdot 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 \times 100 = 10,000) 次状态转移。
第四种方法：通过二分搜索，每次搜索范围减半，最多需要计算 (100 \times \log_2 100 \approx 700) 次状态转移。

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

总结

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

Previous Topic

Back to Lesson

Next Topic

数据结构与算法