[路飞]_leetcode-887-鸡蛋掉落

输入： k = 1, n = 2
输出： 2
解释：
鸡蛋从 1 楼掉落。如果它碎了，肯定能得出 f = 0 。 
否则，鸡蛋从 2 楼掉落。如果它碎了，肯定能得出 f = 1 。 
如果它没碎，那么肯定能得出 f = 2 。 
因此，在最坏的情况下我们需要移动 2 次以确定 f 是多少。 
复制代码

输入： k = 2, n = 6
输出： 3
复制代码

输入： k = 3, n = 14
输出： 4
复制代码

var superEggDrop = (k, n)=> {
  // 特判，如果只有一枚鸡蛋，返回楼层数
  if(k===1) return n;
  // 初始化 dp 数组
  dp = Array(k+1);
  for(let i = 0;i<=k;i++){
    dp[i] = Array(n+1).fill(0)
  }
  // 将鸡蛋为 1 的情况赋值对应楼层
  for(let j = 1;j<=n;j++){
    dp[1][j] = j
  }
  // 利用状态转移方程，推导出 dp[k][n]
  for(let i = 2;i<=k;i++){
    for(let j = 1;j<=n;j++){
      dp[i][j] = j;
      for(let x = 1;x<=j;x++){
        dp[i][j] = Math.min(dp[i][j],Math.max(dp[i-1][x-1],dp[i][j-x])+1)
      }
    }
  }
  // 返回结果
  return dp[k][n];
};
复制代码

var superEggDrop = (k, n)=> {
  // 特判，如果只有一枚鸡蛋，返回楼层数
  if(k===1) return n;
  // 初始化 dp 数组
  dp = Array(k+1);
  for(let i = 0;i<=k;i++){
    dp[i] = Array(n+1).fill(0)
  }
  // 将鸡蛋为 1 的情况赋值对应楼层
  for(let j = 1;j<=n;j++){
    dp[1][j] = j
  }
  // 利用状态转移方程，推导出 dp[k][n]
  for(let i = 2;i<=k;i++){
    for(let j = 1;j<=n;j++){
      dp[i][j] = j;
      // 利用二分查找最优 x 值
      let l = 1,r = j;
      while(l<r){
        const mid = (l+r)>>1;
        if(dp[i-1][mid-1]<dp[i][j-mid]) l = mid+1
        else r = mid
      }
      dp[i][j] = Math.min(dp[i][j],Math.max(dp[i-1][l-1],dp[i][j-l])+1)
    }
  }
  // 返回结果
  return dp[k][n];
};
复制代码

var superEggDrop = (k, n)=> {
  // 特判，如果只有一枚鸡蛋，返回楼层数
  if(k===1) return n;
  // 初始化 dp 数组
  dp = Array(k+1);
  for(let i = 0;i<=k;i++){
    dp[i] = Array(n+1).fill(0)
  }
  // 将鸡蛋为 1 的情况赋值对应楼层
  for(let j = 1;j<=n;j++){
    dp[1][j] = j
  }
  // 利用状态转移方程，推导出 dp[k][n]
  for(let i = 2;i<=k;i++){
    // 通过记忆 x 值优化推导过程
    let x = 1;
    for(let j = 1;j<=n;j++){
      dp[i][j] = j;
      while(dp[i-1][x-1]<dp[i][j-x]) x++
      dp[i][j] = Math.min(dp[i][j],Math.max(dp[i-1][x-1],dp[i][j-x])+1)
    }
  }
  // 返回结果
  return dp[k][n];
};
复制代码

var superEggDrop = (k, n)=> {
  // 特判，如果只有一枚鸡蛋，返回楼层数
  if(k===1) return n;
  // 初始化 dp 数组
  dp = Array(2);
  for(let i = 0;i<2;i++){
    dp[i] = Array(n+1).fill(0)
  }
  // 将鸡蛋为 1 的情况赋值对应楼层
  for(let j = 1;j<=n;j++){
    dp[1][j] = j
  }
  // 利用状态转移方程，推导出 dp[k][n]
  for(let i = 2;i<=k;i++){
    // 通过滚动数组优化空间复杂度
    let cur = i%2,pre = !cur*1;
    // 通过记忆 x 值优化推导过程
    let x = 1;
    for(let j = 1;j<=n;j++){
      dp[cur][j] = j;
      while(dp[pre][x-1]<dp[cur][j-x]) x++
      dp[cur][j] = Math.min(dp[cur][j],Math.max(dp[pre][x-1],dp[cur][j-x])+1)
    }
  }
  // 返回结果
  return dp[k%2][n];
};
复制代码

var superEggDrop = (k, n)=> {
  // 特判，如果只有一枚鸡蛋，返回楼层数
  if(k===1) return n;
  // 初始化 dp 数组
  dp = [Array(k+1).fill(0)];
  // 初始化操作次数
  let cnt = 0;
  // 当 dp[cnt][k] 小于目标楼层的时候，递增操作次数，直到可以测出目标楼层
  while(dp[cnt][k]<n){
    // 递增操作次数
    cnt++
    // 初始化 dp[cnt]
    dp[cnt] = [0]
    // 推导 dp
    for(let j = 1;j<=k;j++){
      dp[cnt][j] = dp[cnt-1][j-1]+1+dp[cnt-1][j]
    }
  }
  // 返回操作次数
  return cnt;
};
复制代码

var superEggDrop = (k, n)=> {
  // 特判，如果只有一枚鸡蛋，返回楼层数
  if(k===1) return n;
  // / 初始化 dp 数组
  const dp = Array(k+1).fill(0);
  // 初始化操作次数
  let cnt = 0;
  // 当 dp[cnt][k] 小于目标楼层的时候，递增操作次数，直到可以测出目标楼层
  // 要注意的是这里的 cnt 没没有表现在 dp 数组中，但是是切实存在的
  while(dp[k]<n){
    // 递增操作次数
    cnt++;
    // 推导 dp
    for(let j = k;j>0;j--){
      dp[j] = dp[j-1]+1+dp[j]
    }
  }
  // 返回操作次数
  return cnt;
};
复制代码