题目地址
https://leetcode.com/problems/super-egg-drop/description/
题目描述
You are given K eggs, and you have access to a building with N floors from 1 to N.
Each egg is identical in function, and if an egg breaks, you cannot drop it again.
You know that there exists a floor F with 0 <= F <= N such that any egg dropped at a floor higher than F will break, and any egg dropped at or below floor F will not break.
Each move, you may take an egg (if you have an unbroken one) and drop it from any floor X (with 1 <= X <= N).
Your goal is to know with certainty what the value of F is.
What is the minimum number of moves that you need to know with certainty what F is, regardless of the initial value of F?
Example 1:
Input: K = 1, N = 2
Output: 2
Explanation:
Drop the egg from floor 1. If it breaks, we know with certainty that F = 0.
Otherwise, drop the egg from floor 2. If it breaks, we know with certainty that F = 1.
If it didn't break, then we know with certainty F = 2.
Hence, we needed 2 moves in the worst case to know what F is with certainty.
Example 2:
Input: K = 2, N = 6
Output: 3
Example 3:
Input: K = 3, N = 14
Output: 4
Note:
1 <= K <= 100
1 <= N <= 10000
思路
这是一道典型的动态规划题目,但是又和一般的动态规划不一样。
拿题目给的例子为例,两个鸡蛋,六层楼,我们最少扔几次?
一个符合直觉的做法是,建立dp[i][j], 代表i个鸡蛋,j层楼最少扔几次,然后我们取dp[K][N]即可。
代码大概这样的:
const dp = Array(K + 1); dp[0] = Array(N + 1).fill(0); for (let i = 1; i < K + 1; i++) { dp[i] = [0]; for (let j = 1; j < N + 1; j++) { // 只有一个鸡蛋 if (i === 1) { dp[i][j] = j; continue; } // 只有一层楼 if (j === 1) { dp[i][j] = 1; continue; } // 每一层我们都模拟一遍 const all = []; for (let k = 1; k < j + 1; k++) { const brokenCount = dp[i - 1][k - 1]; // 如果碎了 const notBrokenCount = dp[i][j - k]; // 如果没碎 all.push(Math.max(brokenCount, notBrokenCount)); // 最坏的可能 } dp[i][j] = Math.min(...all) + 1; // 最坏的集合中我们取最好的情况 } } return dp[K][N];
果不其然,当我提交的时候,超时了。 这个的时复杂度是很高的,可以看到,我们内层暴力的求解所有可能,然后
取最好的,这个过程非常耗时,大概是O(N^2 * K).
然后我看了一位leetcode网友的回答,
他的想法是dp[M][K]means that, given K eggs and M moves,what is the maximum number of floor that we can check.
我们按照他的思路重新建模:
可以看到右下角的部分根本就不需要计算,从而节省很多时间
关键点解析
- dp建模思路要发生变化, 即
dp[M][K]means that, given K eggs and M moves,what is the maximum number of floor that we can check.
代码
/* * @lc app=leetcode id=887 lang=javascript * * [887] Super Egg Drop * * https://leetcode.com/problems/super-egg-drop/description/ * * algorithms * Hard (24.64%) * Total Accepted: 6.2K * Total Submissions: 24.9K * Testcase Example: '1\n2' * * You are given K eggs, and you have access to a building with N floors from 1 * to N. * * Each egg is identical in function, and if an egg breaks, you cannot drop it * again. * * You know that there exists a floor F with 0 <= F <= N such that any egg * dropped at a floor higher than F will break, and any egg dropped at or below * floor F will not break. * * Each move, you may take an egg (if you have an unbroken one) and drop it * from any floor X (with 1 <= X <= N). * * Your goal is to know with certainty what the value of F is. * * What is the minimum number of moves that you need to know with certainty * what F is, regardless of the initial value of F? * * * * * * * * Example 1: * * * Input: K = 1, N = 2 * Output: 2 * Explanation: * Drop the egg from floor 1. If it breaks, we know with certainty that F = 0. * Otherwise, drop the egg from floor 2. If it breaks, we know with certainty * that F = 1. * If it didn't break, then we know with certainty F = 2. * Hence, we needed 2 moves in the worst case to know what F is with * certainty. * * * * Example 2: * * * Input: K = 2, N = 6 * Output: 3 * * * * Example 3: * * * Input: K = 3, N = 14 * Output: 4 * * * * * Note: * * * 1 <= K <= 100 * 1 <= N <= 10000 * * * * * */ /** * @param {number} K * @param {number} N * @return {number} */ var superEggDrop = function(K, N) { // 不选择dp[K][M]的原因是dp[M][K]可以简化操作 const dp = Array(N + 1).fill(0).map(_ => Array(K + 1).fill(0)) let m = 0; while (dp[m][K] < N) { m++; for (let k = 1; k <= K; ++k) dp[m][k] = dp[m - 1][k - 1] + 1 + dp[m - 1][k]; } console.log(dp); return m; };Java中的“ <<”运算符 - java
最喜欢的语句来自Java的Character类:(1 << Character.PARAGRAPH_SEPARATOR)) >> type PARAGRAPH_SEPARATOR是字节,type是整数。这句话中的操作员,他们做什么?如何以及在哪里可以使用这些运算符?这是oracles java.lang.Character文档。该类中…
python setup.py egg_info mysqlclient - python尝试在Python 3.6.0上使用pip3安装mysqlclient$ pip3 install mysqlclient Collecting mysqlclient Using cached mysqlclient-1.3.10.tar.gz Complete output from command python setup.py egg_info: T…
LeetCode题解爱丽丝和鲍勃爱丽丝和鲍勃一起玩游戏,他们轮流行动。爱丽丝先手开局。最初,黑板上有一个数字 N 。在每个玩家的回合,玩家需要执行以下操作:选出任一 x,满足 0 < x < N 且 N % x == 0 。用 N - x 替换黑板上的数字 N 。如果玩家无法执行这些操作,就会输掉游戏。只有在爱丽丝在游戏中取得胜利时才返回 True,否则返回 false。假设两…
Python继承:修改对象的父类 - python我需要/想要修改父类,并且在正确导入时遇到问题。子对象仍然使用该类的“旧”版本。文件A(某些我不想直接修改的lib):class A(object): def __init__(self): self.contentA = "42" print("A.__init__() ausgeführt") def m(self…
LeetCode题解求一根绳子被切两刀能组成一个三角形的概率。如题题解:我们可以设绳长为1,设:- 其中两段长为x, y且x, y都>0- 故第三段长为1-x-y且>0故可以在二维坐标轴画出一个三角形(由x=0;y=0;1-x-y=0围成)要想构成三角形还要满足:- x+y > 1-x-y => x+y > 0.5- x+1-x-y > y => y < 0.5- y+1…