problem#

腾讯大厦有39层，你手里有两颗一模一样的玻璃球，当你拿着玻璃球在某 一层往下扔的时候，一定会有两个结果:玻璃球碎了或者没碎，大厦有个临 界楼层，低于它的楼层，往下扔玻璃球，玻璃球不会碎，等于或者高于它 的楼层，扔下玻璃球一定会碎。玻璃球碎了就不能再扔了。现在让你设计 一种方法，使得在该方法下，最坏情况下扔的次数比其他任何方式最坏的 次数都少，也就是设计一种最有效的方法。请给出正确答案。

ans#

如果你只有一个球，你肯定只会从第一楼一直往上去试；
但现在有两个球，你可能第一想法是二分，

如果第一个球在20扔下去没碎，我就继续二分；
如果碎了，那就退化到只有一个球的场景，一个一个试；

不过，借着这个逻辑，我们现在是把1到39层分成了两份，如果分成四份呢？

分成1到9，10到19，20到29，30到39；  
这样，我们先去试10，如果10不行，那就试1-9；  
如果10行，就去试20；  

以此类推， 那我们最坏的情况会试多少次呢？

对于这种分组，如果10不行，就是1+9=10次；  
如果10行，去试20，  
如果20不行，就是1+1+9=11次；  
如果20行，去试30，
如果30不行，就是1+1+1+9=12次；
如果30行，试不试39的两种最坏情况次数应该是一样的，是1+1+1+9=12次

所以说这样的话最多是12次；
所以可能有结论，分组越多，次数可能越少。？ 细想一下并不是这样，极限情况下我分成39组，那又回到挨个试一下的情况了；
那有没有什么一劳永逸的办法或者从数学公式的底层原理推导一下呢？
有的，兄弟，有的。

这涉及到了动态规划的内容,Dynamic Programming

设dp[n][m]表示n层大厦，m个球最坏情况下扔的次数；
那么会分两种情况；
假设我们现在在第k层扔下去了球；

当第 m 个球扔下去没碎时，那就相当于接下来从 n-k 这么高的楼去扔 m 个球找次数
当第 m 个球扔下去碎了时，那我们就要在 k-1 这么高的楼去扔 m-1 个球去找次数

同时别忘了你试的这一次；

然后我们遍历k，找他们的最小值，就是我们的最小次数

所以递推公式为

dp[n][m]=min(max(dp[n-k][m],dp[k-1][m-1])+1), m>=2

初始条件为

dp[n][1]=n

cpp代码为

#include <bits/stdc++.h>
using namespace std;
int main(){
    int dp[101][5]={0};
    int n,m;
    cin >> n >> m;
    for(int i=0;i<=n;i++){
        dp[i][1]=i;
    }
    for(int a=2;a<=m;a++){
        for(int t=1;t<=n;t++){
            if(t<=a){
                dp[t][a]=t;
            }else{
                int x=10000;//这个数至少为9，但是你要是知道9了，这题答案就出来了
                for(int k=1;k<=t;k++){
                    x=min(x,max(dp[k-1][a-1],dp[t-k][a])+1);
                }
                dp[t][a]=x;
            }
        }
    }
    cout << dp[n][m];
    return 0;
}

input

39 2

output

9