动态规划(1)
/** * 动态规划 * @param floorNum 楼层数 * @param eggNum 鸡蛋数 * @return 在最怀情况下，鸡蛋最多下落的次数 */ int getFloor(int floorNum,int eggNum){ int[][] f=new int[eggNum+1][floorNum+1]; for(int j=0;j<=floorNum;j++){ f[1][j]=j; f[0][j]=0; } if (eggNum==1){ return floorNum; } for(int i=2;i<=eggNum;i++){ f[i][0]=0; //从低层依次住上下落 for(int j=1;j<=floorNum;j++){ f[i][j]=0; //计算f(eggNum,k)=f(eggNum-1,k-1)+f(eggNum-1,k-2)+....+f(eggNum-1,0)+k for(int q=1;q<=j;q++){ f[i][j] += f[i-1][q-1]; } f[i][j] +=j;//此处使用j,开始写成了k //比较第一次在j层落下时，最大测试的楼层数与总楼层数 if(f[i][j]>=floorNum){ //如果超过总楼层数且等于鸡蛋数量，则返回，否则不必再计算 if(i==eggNum) { return j; }else{ break; } } } } return 0; }动态规划(2）
/** * * @param floorNum 楼层数 * @param eggNum 鸡蛋数 * @return 最坏情况下，至多测试的次数 */ int getFloor(int floorNum,int eggNum){ for(int i=1;i<=floorNum;i++){ if(f(eggNum,i)>=floorNum){ return i; } } return 0; } /** * * @param eggNum 鸡蛋数量 * @param k K次尝试 * @return 最大测试的楼层数 */ int f(int eggNum,int k){ int[][] f=new int[eggNum+1][k+1]; for(int j=0;j<=k;j++){ f[1][j]=j; f[0][j]=0; } if (eggNum==1){ return f[1][k]; } for(int i=2;i<=eggNum;i++){ f[i][0]=0; for(int j=1;j<=k;j++){ f[i][j]=0; //计算f(eggNum,k)=f(eggNum-1,k-1)+f(eggNum-1,k-2)+....+f(eggNum-1,0)+k for(int q=1;q<=j;q++){ f[i][j] += f[i-1][q-1]; } f[i][j] +=j;//此处使用j,开始写成了k } } return f[eggNum][k]; } 测试3个鸡蛋，100层楼
第二种思路-递归:第9层,耗时0ms 第二种思路-动态规划1:第9层,耗时0ms 第二种思路-动态规划2:第9层,耗时0ms 第一种思路-动态规划:第9层,耗时1ms10个鸡蛋,10000层楼
第二种思路-递归:第14层,耗时0ms 第二种思路-动态规划1:第14层,耗时1ms 第二种思路-动态规划2:第14层,耗时0ms 第一种思路-动态规划:第14层,耗时478ms2个鸡蛋,100000层楼
第二种思路-递归:第447层,耗时2ms 第二种思路-动态规划1:第447层,耗时2ms 第二种思路-动态规划2:第447层,耗时36ms 第一种思路-动态规划:第447层,耗时5281ms60鸡蛋,10000000层楼
第二种思路-递归:第24层,耗时102ms 第二种思路-动态规划1:第24层,耗时641ms 第二种思路-动态规划2:第24层,耗时16ms 第一种思路运行中.....可以看出，第一种思路实现方式运行是最慢的，因为需要从小到大(eggNum从2开始，floorNum从1开始)循环嵌套计算二维数组第一项的值。而第二种思路动态规划2，当得出的层数较矮时，优势明显，层数比较多时，就慢于第二种思路动态规划1，因为动态规划2，得到的结果楼层越矮时计算的越快，而动态规划1也是嵌套循环计算，但只要计算到可测试最大楼层大于或等于总楼层就停止计算，比第一种思路的动态规划要快。所以没有哪一种算法是最优的，需要根据数据量的多少来决定采取哪一种实现方法。