AcWing1048 鸡蛋的硬度（浅谈两种解法的思考方向）

2021-03-11 08:33

阅读：567

标签：splay ide 最好面试题思想 div src 区间规划

这是经典的谷歌面试题，也是经典的动态规划问题

根据y总的说法，动态规划问题要划分集合，表示状态

对于这道题，有两个经典的解法，他们的复杂度不同，因为对状态的定义略有不同

1.最常规的思想，设计状态为前i层用j个鸡蛋所能测的最坏情况的最小值是多少

我相信集合的定义很多人能想到，但是状态的定义还需要进行分析

首先，为什么是最坏情况，因为我们不知道鸡蛋什么时候会碎，这是未知的，所以要考虑最坏的情况，而最小值是因为，这是我们能控制的。

所以不能控制的要考虑最坏，能控制的要考虑最好

那么状态转移方程就能定义为f[i][j-1]和max(f[i-k][j],f[k-1][j-1]]+1中的最小值，因为我们在考虑测试的时候，可以在1-i中任选一个地方开始测，但是我们不能知道在我们选的地方蛋会不会碎

另外，还可以不适用鸡蛋，也就是直接沿用f[i][j-1]的情况

#include
#include
using namespace std;
const int N=1010;
int f[N][N];
int main(){
    int i,j;
    int n,m;
    while(cin>>n>>m){
    
    for(i=1;i){
        f[i][1]=i;
    }
    for(i=1;i){
        f[1][i]=1;
    }
    for(i=2;i){
        for(j=2;j){
            f[i][j]=f[i][j-1];
            int k;
            for(k=1;k){
                f[i][j]=min(f[i][j],max(f[i-k][j],f[k-1][j-1])+1);
            }
        }
    }
    coutendl;}
}

View Code

2.上面的复杂度比较高，那是因为我们要选一个地方进行测试，所以要多枚举一维。第二种方法更加巧妙

我们定义f[i][j]为用j个鸡蛋测量i次最多能测多长的区间，我们能想到这个状态的原因是，动态规划的划分依据一般从题目所给信息想出，我们既然不想枚举位置，那么就把长度当作状态量，而把次数和个数当作状态。

这样的话就能用f[i-1][j-1]+f[i-1][j]+1,这个意思是，如果蛋碎了，那就是测i-1次用j-1个鸡蛋的长度，不然就是i-1次用j个鸡蛋的长度，因为蛋的情况只有一种，所以两个集合独立，可以相加，而他们相加就是最终的答案

#include
#include
using namespace std;
const int N=1010;
int f[N][N];
int main(){
    int i,j;
    int n,m;
    while(cin>>n>>m){
        for(i=1;i){
            for(j=1;j){
                f[i][j]=f[i-1][j]+f[i-1][j-1]+1;
                
            }
            if(f[i][m]>=n){
                    coutendl;
                    break;
            }
        }
    }
}

View Code

AcWing1048 鸡蛋的硬度（浅谈两种解法的思考方向）

标签：splay ide 最好面试题思想 div src 区间规划

原文地址：https://www.cnblogs.com/ctyakwf/p/12641124.html

上一篇：Windows Server 2016 - 关闭按Ctrl+Alt+Del才能登录

下一篇：JAVA基础知识总结

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing1048 鸡蛋的硬度（浅谈两种解法的思考方向）
文章链接：http://soscw.com/index.php/essay/63129.html

亲，登录后才可以留言！

AcWing1048 鸡蛋的硬度（浅谈两种解法的思考方向）

评论

热门文章

推荐文章

最新文章

置顶文章