网站设计在线培训,卖货平台有哪些,wordpress加入移动端导航栏,微信开发者模式在哪题目大意#xff1a; 你有k个鸡蛋#xff0c;对n层楼的建筑#xff0c;请确认在f层扔鸡蛋鸡蛋恰好不会破碎的最少次数#xff08;f满足 0 f n#xff09;。
方法一#xff1a; 状态#xff1a;即会发生变化的量#xff0c;很明显有两个#xff0c;当前拥有…题目大意 你有k个鸡蛋对n层楼的建筑请确认在f层扔鸡蛋鸡蛋恰好不会破碎的最少次数f满足 0 f n。
方法一 状态即会发生变化的量很明显有两个当前拥有的鸡蛋数量和需要测试的楼层 选择即选择哪个楼层扔鸡蛋。 dp(n,k)是你在所有楼层中选择一个在最坏情况下需要的操作次数最小的楼层扔鸡蛋 代码
class Solution {MapString,Integermem new HashMap();public int superEggDrop(int k, int n) {return dp(k,n);}// n为当前找寻的楼层数private int dp(int k, int n) {if(k1)return n;if(n0)return 0;String curKey k , n;if(mem.containsKey(curKey)) {return mem.get(curKey);}int res Integer.MAX_VALUE;for(int i1;in;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[k1][n1];int m0;while(dp[k][m]n) {m;for(int i1;ik;i) {// 碎了的话测试楼下没碎的话测试楼上dp[i][m]dp[i-1][m-1] dp[i][m-1]1;}}return m;}}
