leetcode 887 ——扔鸡蛋

鸡蛋"/>

leetcode 887 ——扔鸡蛋

题目大意：
你有k个鸡蛋，对n层楼的建筑，请确认在f层扔鸡蛋鸡蛋恰好不会破碎的最少次数（f满足 0 <= f <= n）。

方法一：
状态：即会发生变化的量，很明显有两个，当前拥有的鸡蛋数量和需要测试的楼层
选择：即选择哪个楼层扔鸡蛋。
dp(n,k)，是你在所有楼层中选择一个在最坏情况下需要的操作次数最小的楼层扔鸡蛋；
代码：
 

class Solution {Map<String,Integer>mem = new HashMap<>();public int superEggDrop(int k, int n) {return dp(k,n);}// n为当前找寻的楼层数private int dp(int k, int n) {if(k==1)return n;if(n==0)return 0;String curKey = k + "," +n;if(mem.containsKey(curKey)) {return mem.get(curKey);}int res = Integer.MAX_VALUE;for(int i=1;i<=n;i++) {// 找所有楼层中最坏情况下操作次数最小的楼层扔鸡蛋res = Math.min(res, Math.max(dp(k-1,i-1), dp(k,n-i))+1);}mem.put(curKey, res);return res;}
}

方法二：
状态：当前拥有的鸡蛋数量k和测试次数m，
选择：每次鸡蛋碎或者不碎总的测试获取的楼层数量都为楼上的层数 + 楼下的楼层数 + 1
dp(k,m)，代表在k个鸡蛋的情况下，扔m次在最坏情况下的测试楼层数量。
代码：
 

class Solution {public int superEggDrop(int k, int n) {int [][]dp = new int[k+1][n+1];int m=0;while(dp[k][m]<n) {m++;for(int i=1;i<=k;i++) {// 碎了的话测试楼下，没碎的话测试楼上dp[i][m]=dp[i-1][m-1]+ dp[i][m-1]+1;}}return m;}}