动态规划解决鸡蛋掉落问题

这篇具有很好参考价值的文章主要介绍了动态规划解决鸡蛋掉落问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

问题描述

解决问题

①蛮力法

②备忘录

③递归改递推

④二分法

⑤逆向思维


问题描述

给定一定楼层数的建筑物和一定数量的鸡蛋,求出可以找出门槛楼层的最少鸡蛋掉落实验的次数,约束条件是:幸存的鸡蛋可以重复使用,破碎的鸡蛋不能再次使用,如果鸡蛋从此层掉落会碎,那么从更高的楼层掉落也会碎,如果鸡蛋从此层掉落不会碎,那么从更低的楼层掉落也不会碎。

解决问题

我们先来看只有一个鸡蛋的情况,如图1所示,由于鸡蛋会破碎不可再次使用,所以我们只能从最低的楼层开始扔鸡蛋,如果在第一层楼扔鸡蛋没有碎,那么继续往上也就是第二层扔鸡蛋,如果鸡蛋在某一层扔碎了,那么说明门槛楼层就是这一层。这样要找出门槛楼层的最少扔鸡蛋的次数就是楼层的层数。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

图1 只有一个鸡蛋的情况

那如果我们有足够多的鸡蛋,即鸡蛋数大于等于楼层数,如图2所示,我们可以先随便在一个楼层扔一个鸡蛋看看会发生什么。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

图2 有足够多的鸡蛋

比如说我们选择在3楼扔出一个鸡蛋,如图3所示。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

图3 在3楼扔出一个鸡蛋

那么事实是扔出的鸡蛋会有两种结果,一种情况是鸡蛋在3楼扔下破碎了,那么说明我们要找的门槛楼层在3楼以下的楼层,如图4所示,同时我们可以用的鸡蛋减少了一个,即问题的规模减少。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

图4 鸡蛋破碎的情况

还有一种情况是鸡蛋从3楼扔下去没碎,那么我们刚刚扔下去的鸡蛋还可以再重复使用,也就是可用的鸡蛋数没有减少,同时说明我们要找的门槛楼层在3楼以上,如图5所示,这样问题的规模也减小了。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

图5 鸡蛋没碎的情况

我们记Time[egg][height]为egg个鸡蛋和height高的楼层要找出门槛楼层所需要的扔鸡蛋的次数,通过刚刚的分析,我们知道要求解Time[egg][height]可以先在high层扔一次鸡蛋,那么Time[egg][height]的值就应该为Time[egg-1] [high-1](鸡蛋碎了,鸡蛋数减少一个,楼层数减少一层)和Time[egg][height-high](鸡蛋没碎,鸡蛋数没变,楼层往上)的较大值加一(因为我们扔了一次鸡蛋),所以可以得出下面的状态转移方程:

Time[egg][height]=1+max (Time[egg-1] [high-1], Time[egg][height-high])

通过上面的分析,我们可以知道,要求解Time[egg][height]可以通过求解其子问题Time[egg-1] [high-1]和Time[egg][height-high]来实现。

因为我们要找出最少的扔鸡蛋的次数,所以要在所有楼层扔鸡蛋的情况中寻找最小值,更准确的状态转移方程应该是下面这个:

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

①蛮力法

蛮力法即直接枚举所有楼层扔鸡蛋的情况,如图6所示,把在每一层楼扔鸡蛋的情况都计算一遍,找出其中的最小值。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

图6 蛮力法枚举所有情况

采用纯递归的方法,可以对所有可能的楼层进行遍历,计算在这一层扔鸡蛋所需的最小尝试次数。具体地,对于第i层楼,需要递归调用函数,在第i层扔鸡蛋和在第i层楼上方继续搜索两种情况下,所需的尝试次数取二者中的最大者,再加上一次实际的尝试机会,即可得到在第i层楼扔鸡蛋的最小尝试次数。

纯递归的时间复杂度非常高,随楼层数的增加指数增长,随鸡蛋数的增加线性增长。

C++代码

//
// Created by YEZI on 2023/5/15.
//

#ifndef EGGDROP_BRUTE_H
#define EGGDROP_BRUTE_H
#include<iostream>
namespace brute{
    int superEggDrop(int egg,int height){
        if(egg==1||height<=2)
            return height;
        int minTimes=height;
        for(int i=1;i<=height;i++){
            minTimes=std::min(minTimes,std::max(superEggDrop(egg,i-1), superEggDrop(egg-1,height-i))+1);
        }
        return minTimes;
    }
}
#endif //EGGDROP_BRUTE_H

测试

我们先在LeetCode上提交代码进行测试,测试结果如图7所示,可见蛮力法通过了32个测试样例,验证了算法的正确性,但是在鸡蛋数为3、楼层数为26的时候超出了时间的限制。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

图7 LeetCode蛮力法测试

我们固定楼层数为20层,测试不同鸡蛋数的结果如图8所示,符合线性增长的预测。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

图8 蛮力法 固定楼层数

具体数据如表1所示。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

表1 蛮力法 固定楼层数

固定鸡蛋的个数为10个,测试不同楼层的结果如图9所示,符合指数增长。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

图9 蛮力法 固定鸡蛋数

具体数据如表2所示。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

表2 蛮力法 固定鸡蛋数

结果分析

由结果可知,纯递归的暴力枚举的执行效率比较差,速度非常慢,由于没有将每个子问题的解记录下来,每次都需要重新计算子问题的解,重复计算大大增加,加上递归调用函数的开销也很大,其计算的时间效率随楼层数的增加呈指数增长,随鸡蛋数的增加线性增长,

因此我们需要对算法进行优化。

②备忘录

纯递归的暴力枚举重复计算了子问题的解,因此我们可以开辟二维数组将计算过程的子问题的解记录下来,这样将不再需要重新计算子问题的解,时间复杂度为O(egg*height^2),空间复杂度为O(egg*height)。

C++代码 

//
// Created by YEZI on 2023/5/15.
//

#ifndef EGGDROP_DYNAMICPROGRAM_H
#define EGGDROP_DYNAMICPROGRAM_H
#include<iostream>
namespace dynamicProgram{
    int **dp;
    int Drop(int egg,int height){
        if(dp[egg][height]!=-1){
            return dp[egg][height];
        }
        if(egg==1||height<=2){
            dp[egg][height]=height;
            return height;
        }
        int minTimes=height;
        for(int i=1;i<=height;i++){
            minTimes=std::min(minTimes,std::max(Drop(egg,i-1), Drop(egg-1,height-i))+1);
        }
        dp[egg][height]=minTimes;
        return minTimes;
    }

    int superEggDrop(int egg,int height){
        dp=new int*[egg+1];
        for(int i=1;i<=egg;i++){
            dp[i]=new int[height+1];
        }
        for(int i=1;i<=egg;i++){
            for(int j=0;j<=height;j++){
                dp[i][j]=-1;
            }
        }
        return Drop(egg,height);
    }
}
#endif //EGGDROP_DYNAMICPROGRAM_H

测试

我们先在LeetCode上提交代码进行测试,测试结果如图10所示,可见备忘录法通过了67个测试样例,比先前的通过个数更多了,验证了算法的正确性,但是在鸡蛋数为5、楼层数为2000的时候超出了时间的限制。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

图10 LeetCode备忘录测试

固定楼层数为500层,测试不同鸡蛋个数的结果如图11所示,符合线性增长。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

图11 备忘录 固定楼层数

具体数据如表3所示。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

表3 备忘录 固定楼层数

固定鸡蛋的个数为10个,测试不同楼层的结果如图12所示,符合平方增长。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

图12 备忘录 固定鸡蛋数

具体数据如表4所示。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

表4 备忘录 固定鸡蛋数

结果分析

由结果可以看出,与之前的暴力枚举相比,我们将每个子问题的解记录下来的优化效果十分明显,可以测试的数据规模明显增长,但是我们仍然没有在规定时间内通过LeetCode上的所有测试用例,我们还需要继续优化算法。

③递归改递推

我们先前两个策略都是采用递归调用函数实现的,反复递归调用函数的开销很大,因此我们在备忘录的基础上将递归调用函数改为循环内递推,时间复杂度和空间复杂度和备忘录相比没有变化,但理论上递推执行起来会更快。

C++代码

//
// Created by YEZI on 2023/5/21.
//

#ifndef MAIN_CPP_ITERATIVEDP_H
#define MAIN_CPP_ITERATIVEDP_H
#include<iostream>
namespace iterativeDP{
    int superEggDrop(int egg,int height){
        int **dp=new int*[egg+1];
        for(int i=1;i<=egg;i++){
            dp[i]=new int[height+1];
            dp[i][0]=0;
            dp[i][1]=1;
        }
        for(int i=1;i<=height;i++){
            dp[1][i]=i;
        }
        for(int i=2;i<=egg;i++){
            for(int j=2;j<=height;j++){
                dp[i][j]=height;
                for(int k=1;k<=j;k++){
                    dp[i][j]=std::min(dp[i][j],std::max(dp[i-1][k-1],dp[i][j-k])+1);
                }
            }
        }
        return dp[egg][height];
    }
}
#endif //MAIN_CPP_ITERATIVEDP_H

测试

我们先在LeetCode上提交代码进行测试,测试结果如图13所示,可见递推法通过了74个测试样例,与之前的相比通过的个数更多了,验证了算法的正确性,但是在鸡蛋数为6、楼层数为10000的时候还是超出了时间的限制。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

图13 LeetCode 递推测试

固定楼层数为500层,测试不同鸡蛋个数的结果如图14所示,符合线性增长的预测。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

图14 递推固定楼层数

具体数据如表5所示。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

表5 递推固定楼层数

固定鸡蛋个数为10个,测试不同楼层数的结果如图15所示。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

图15 递推固定鸡蛋数

具体数据如表6所示。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

表6 递推固定鸡蛋数

结果分析

由结果可以看出来,递推法相比备忘录的速度更快了,但是还是没有在规定时间内通过LeetCode上的所有测试用例,我们还得继续努力。

④二分法

先前我们是暴力枚举了所有楼层扔鸡蛋的情况去找最小的测试次数,但事实上我们可能并不需要把每一个情况都计算一次。我们通过求解子问题Time[egg-1][high-1](鸡蛋破碎的情况,可用的鸡蛋个数减一,楼层数减一)和子问题Time[egg][height-high](鸡蛋没碎的情况,楼层数减少),我们要求二者的较小值,而从数学上,Time[egg-1][high-1]是high单调递增的函数,Time[egg][height-high]是high单调递减的函数,如图16所示,我们可以通过二分法找到满足要求的high值,从而将把时间复杂度从原本的O(egg*height^2)缩小为O(egg*height*log(height))。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

图16 二分法

C++代码

//
// Created by YEZI on 2023/5/21.
//

#ifndef MAIN_CPP_DICHOTOMY_H
#define MAIN_CPP_DICHOTOMY_H

#include<iostream>

namespace dichotomy {
    int superEggDrop(int egg, int height) {
        int **dp = new int *[egg + 1];
        for (int i = 1; i <= egg; i++) {
            dp[i] = new int[height + 1];
            dp[i][0] = 0;
            dp[i][1] = 1;
        }
        for (int i = 1; i <= height; i++) {
            dp[1][i] = i;
        }
        for (int i = 2; i <= egg; i++) {
            for (int j = 2; j <= height; j++) {
                int low = 1;
                int high = j;
                while (low < high) {
                    int mid = (low + high + 1) / 2;
                    if (dp[i - 1][mid - 1] <= dp[i][j - mid]) {
                        low = mid;
                    } else {
                        high = mid - 1;
                    }
                }
                dp[i][j] = std::max(dp[i - 1][low - 1], dp[i][j - low]) + 1;
            }
        }
        return dp[egg][height];
    }
}
#endif //MAIN_CPP_DICHOTOMY_H

测试

我们先在LeetCode上提交代码进行测试,测试结果如图17所示,可见二分法优化的效果非常明显,终于通过了所有的测试用例,耗时324ms,内存消耗25.4MB。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

图17 LeetCode 二分法测试

固定楼层数为10000层,测试不同鸡蛋个数的结果如图18所示,符合线性增长的预测。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

图18 二分法 固定楼层数

具体数据如表7所示。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

表7 二分法 固定楼层数

固定鸡蛋个数为10个,测试不同楼层数的结果如图19所示,符合对数增长的预测。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

图19 二分法 固定鸡蛋数

具体数据如表8所示。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

表8 二分法 固定鸡蛋数

结果分析

由结果可知,二分优化的效果非常明显,无论是执行速率还是可以处理的数据规模和之前的相比都有非常大的提升。

⑤逆向思维

我们可以将问题反过来想,对于给定time次尝试,egg个鸡蛋,我们可以测出多少层。我们定义high[egg]为egg个鸡蛋可以测出的层数,那么每一次尝试中,egg个鸡蛋可以测试出的层数就应该等于上一次尝试中egg个鸡蛋可以测出的层数加上本次egg个鸡蛋可能测出的层数,即:

high[egg]=1+high[egg]+high[egg-1]

而对于要解决鸡蛋掉落问题,我们只需要一次一次的尝试,直到high[egg]大于等于所给定的楼层数即可。

这个算法的空间复杂度为O(egg),时间复杂度为O(egg*height),事实上,更确切的时间复杂度为动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

C++代码 

//
// Created by YEZI on 2023/5/21.
//

#ifndef MAIN_CPP_BACKWARD_H
#define MAIN_CPP_BACKWARD_H
namespace backward{
    int superEggDrop(int egg,int height){
        int*high=new int[egg+1];
        for(int i=0;i<=egg;i++){
            high[i]=0;
        }
        int times=0;
        while(high[egg]<height){
            times++;
            for(int i=egg;i>0;i--){
                high[i]=high[i]+high[i-1]+1;
            }
        }
        return times;
    }
}
#endif //MAIN_CPP_BACKWARD_H

测试

我们先在LeetCode上提交代码进行测试,测试结果如图20所示,逆向思维方法通过了所有的测试用例,而且更快,耗时0ms,内存消耗5.9MB。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

图20 LeetCode逆向思维测试

固定楼层数为一百万层,测试不同鸡蛋个数的结果如图21所示,符合线性增长的预测。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

图21 逆向思维法 固定楼层数

具体数据如表9所示。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

表9 逆向思维法 固定楼层数

固定鸡蛋数为1000000个,测试不同楼层数的结果如图22所示,符合预测。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

图22 逆向思维法 固定鸡蛋个数

具体数据如表10所示。

动态规划解决鸡蛋掉落问题,算法设计与分析,动态规划,算法

表10 逆向思维法 固定鸡蛋个数

结果分析

由结果可以看出,该优化策略效果非常明显,运行速度非常之快,能够处理的规模非常大,百万级别的数据也可以在毫秒级别解决。文章来源地址https://www.toymoban.com/news/detail-629862.html

到了这里,关于动态规划解决鸡蛋掉落问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 资源分配问题【算法设计与分析】<动态规划问题>

    问题分析: ( 要把问题分为多步解决,每步求出子问题的多个最优策略后一步依赖于上一步的最有策略,最后一步得出问题的解) (1)首先要考虑分配给项目A的资金与利润的关系。得到此时投资数x与其相对应的 的关系。 (2)其次要考虑分配给前两个项目A,B的总资金 与利

    2023年04月08日
    浏览(39)
  • 【入门dp】力扣鸡蛋掉落问题和转账问题的关系初探

    我昨晚偶然编出了一道水题,名为转账问题:已知银行卡里有不超过 n 元,你想把卡里所有钱提到某信支付,但你无法看到卡里的钱,你只能执行若干次转账 i 元的操作,每次看到转账成功与失败的提示。问至少需要操作多少次。 n 和 i 是自然数。形式化描述:你的策略 y 是

    2024年02月16日
    浏览(36)
  • 算法分析与设计——动态规划求解01背包问题

    假设有四个物品,如下图,背包总容量为8,求背包装入哪些物品时累计的价值最多。 我们使用动态规划来解决这个问题,首先使用一个表格来模拟整个算法的过程。 表格中的信息表示 指定情况下能产生的最大价值 。例如, (4, 8)表示在背包容量为8的情况下,前四个物品的最

    2024年02月04日
    浏览(72)
  • 算法设计与分析之动态规划问题和具体实例

           动态规划(Dynamic Programming,DP)算法通常用于求解某种具有最优性质的问题。在这类问题中,可能会有许多可行解,每一个解都对应一个值,我们希望找到具有最优值的解。         动态规划算法与分治法类似,其基本思想也是将待求解的问题分解成若干个子问题,先

    2024年01月19日
    浏览(40)
  • 【计算机算法设计与分析】图像压缩问题(C++_动态规划)

    在计算机中常用像素点灰度值序列 { p 1 , p 2 , . . . , p n } { p_1, p_2, ..., p_n } { p 1 ​ , p 2 ​ , ... , p n ​ } 表示图像。其中整数 p i ( 1 ≤ i ≤ n ) p_i(1leq i leq n) p i ​ ( 1 ≤ i ≤ n ) ,表示像素点i的灰度值。通常灰度值的范围是0~255。因此,需要用8位表示一个像素。 图像的变位压

    2024年02月03日
    浏览(50)
  • 算法设计与分析实验二:动态规划法求解TSP问题和01背包问题

    【实验内容】 (1)tsp问题:利用动态规划算法编程求解TSP问题,并进行时间复杂性分析。 输入:n个城市,权值,任选一个城市出发; 输出:以表格形式输出结果,并给出向量解和最短路径长度。 (2)01背包问题:利用动态规划算法编程求解0-1背包问题,并进行时间复杂性分

    2024年02月03日
    浏览(58)
  • 动态规划算法解决背包问题,算法分析与C语言代码实现,时间效率解析

    🎊【数据结构与算法】专题正在持续更新中,各种数据结构的创建原理与运用✨,经典算法的解析✨都在这儿,欢迎大家前往订阅本专题,获取更多详细信息哦🎏🎏🎏 🪔本系列专栏 -  数据结构与算法_勾栏听曲_0 🍻欢迎大家  🏹  点赞👍  评论📨  收藏⭐️ 📌个人主

    2023年04月16日
    浏览(50)
  • 算法分析与设计-数字三角形问题(动态规划)(通俗易懂,附源码和图解,含时间复杂度分析)(c++)

    (一)题目 问题描述 给定一个由 n n n 行数字组成的数字三角形,如图所示。 试设计一个算法,计算从三角形的顶至底的一条路径,使该路径经过的数字总和最大。 算法设计 对于给定的由 n n n 行数字组成的数字三角形,计算从该三角形的顶至底的路径经过的数字和的最大值

    2023年04月10日
    浏览(45)
  • 算法分析与设计--动态规划

    一、动态规划简介 二、动态规划求解步骤 三、动态规划典型应用 数字三角形问题 最大子段和问题 0-1背包问题 四、最长公共子序列问题 动态规划求解 五、总结 算法语言--java语言 动态规划算法通常用于求解具有某种最优性质的问题。动态规划与分治算法类似,其基本思想也

    2024年02月07日
    浏览(71)
  • 算法设计与分析复习--动态规划

    算法设计与分析复习–递归与分治(二) 与分析法类似:将原问题分解为子问题 不同点:不是通过递归的方式,而是自底向上的求解问题 矩阵连乘的次数是左矩阵行列,右矩阵行列取出左右中进行相乘。 由于矩阵乘积需要满足左矩阵列等于右矩阵的行,所以可以用一维数组

    2024年02月04日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包