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

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

根据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]的情况

AcWing1048 鸡蛋的硬度(浅谈两种解法的思考方向)
#include<iostream>
#include<algorithm>
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<=n;i++){
        f[i][1]=i;
    }
    for(i=1;i<=m;i++){
        f[1][i]=1;
    }
    for(i=2;i<=n;i++){
        for(j=2;j<=m;j++){
            f[i][j]=f[i][j-1];
            int k;
            for(k=1;k<=i;k++){
                f[i][j]=min(f[i][j],max(f[i-k][j],f[k-1][j-1])+1);
            }
        }
    }
    cout<<f[n][m]<<endl;}
}
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个鸡蛋的长度,因为蛋的情况只有一种,所以两个集合独立,可以相加,而他们相加就是最终的答案

AcWing1048 鸡蛋的硬度(浅谈两种解法的思考方向)
#include<iostream>
#include<algorithm>
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<=n;i++){
            for(j=1;j<=m;j++){
                f[i][j]=f[i-1][j]+f[i-1][j-1]+1;
                
            }
            if(f[i][m]>=n){
                    cout<<i<<endl;
                    break;
            }
        }
    }
}
View Code

 

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

上一篇:VMware虚拟机12.0.1 中 安装Ubuntu 16.04.5 详细步骤参考


下一篇:【Windows编程——API】双人五子棋