好久以前就见过这道谷歌面试题，大概知道要分层，dp代码写不出。不懂就搜啊！
最佳策略表示分的层数要好，最坏运气表示必须要测到最后一下才得到结果。
dp[i][j]表示测i层楼有j个手机在运气最坏的情况下最多需要测多少次。k表示分层的楼数。
1.对于dp[i][1]=i，只有一个手机肯定要从下一层一层往上摔
2.当j>=2时，就可以采用分层的思想。例如分层k=100,j=2。
第一支手机先放100层摔一下，
不坏就血赚，前100层都不用测了；1000层还有900层。下一次放在200层摔一下,没坏就下次就300层，坏了则只剩1只手机下次就201层开始。
换了大赚特赚，直接定位在100层内，只要再测99层就好。下一次从第1层开始测起。
3.可以想到摔坏得只剩1只手机时，可以利用dp[i][1]=i这个贡献。这样可以得出我们扔手机问题具有最优子结构性质。
摔坏了用dp[k-1][j-1]+1表示，表示还要测k-1层，手机数-1，+1表示本次摔的。
没摔坏用dp[i-k][j]+1表示，表示还要测i-k层，手机数不变，+1表示本次摔的。
import java.util.*; public class Main { public static void main(String[] args) { Scanner scan=new Scanner(System.in); int [][] dp=new int[1005][4];//dp[i][j]表示确定i层有j只手机的情况摔多少次 int n=1000; int m=3; for(int i=1;i<=n;i++) dp[i][1]=i;//只有1只手机只能稳妥起见 每层摔一下 for(int j=2;j<=m;j++) { for(int i=1;i<=n;i++) { dp[i][j]=2000;//初始化巨大状态 for(int k=2;k<=i;k++) {//分k层 dp[i][j]=Math.min( dp[i][j] , 1+Math.max(dp[i-k][j], dp[k-1][j-1])); //没摔坏就多测了k层，摔坏就变成k-1层并且手机数-1 } } } System.out.println(dp[n][m]); } }
天上不会掉馅饼，努力奋斗才能梦想成真。——习大大
原文：https://www.cnblogs.com/shoulinniao/p/12392546.html