887.鸡蛋掉落

[arshelia]

问题描述

https://leetcode-cn.com/problems/super-egg-drop/

解题思路

1.动态规划

[arshelia]

/**
 * @param {number} K
 * @param {number} N
 * @return {number}
 */
var superEggDrop = function(k, n){
 var dp = new Array();
 for(let i = 0; i <= n; i++){
   dp[i] = new Array();
   for(j = 0; j <= k; j++ ){
    dp[i][j] = Infinity;
   }
 }
 dp[1][0] = 0;
 dp[0][0] = 0;
 for(let j = 1; j <= k; j++){
   dp[1][j] = 1;
   dp[0][j] = 0;
 }
 for(let i = 0; i <=n; i++){
  dp[i][0] = 0;
  dp[i][1] = i;
 }
 for(let i = 2; i <= n; i++){
   for(let j = 2; j <= k; j++){
    for (let l = 1; l <= i; l++) {
      // 碎了，就需要往低层继续扔：层数少 1 ，鸡蛋也少 1
      // 不碎，就需要往高层继续扔：层数是当前层到最高层的距离差，鸡蛋数量不少
      // 两种情况都做了一次尝试，所以加 1
      dp[i][j] = Math.min(dp[i][j], Math.max(dp[l - 1][j - 1], dp[i - l][j]) + 1);
    }
   }
 }
 return dp[n][k];
}