887. 雞蛋掉落

你將獲得?K?個雞蛋，并可以使用一棟從?1?到?N??共有 N?層樓的建筑。

每個蛋的功能都是一樣的，如果一個蛋碎了，你就不能再把它掉下去。

你知道存在樓層?F ，滿足?0 <= F <= N 任何從高于 F?的樓層落下的雞蛋都會碎，從?F?樓層或比它低的樓層落下的雞蛋都不會破。

每次移動，你可以取一個雞蛋（如果你有完整的雞蛋）并把它從任一樓層?X?扔下（滿足?1 <= X <= N）。

你的目標是確切地知道 F 的值是多少。

leetcode815，無論 F 的初始值如何，你確定 F 的值的最小移動次數是多少？

思路

和藍橋杯的一題扔手機的差不多

①雞蛋沒碎可以繼續用，dp(K,N)表示K個雞蛋，N層樓的最少移動次數。dp(K,N)=1≤X≤Nmin?(max(dp(K?1,X?1),dp(K,N?X)))

時間復雜度為KN2，超時

②基于最優策略的動態規劃，假設x是最優解。dp(K,N)=max(dp(K?1,X?1),dp(K,N?X))，由于dp(K?1,X?1),單調增，dp(K,N?X)單調減，所以當max(dp[k-1][x-1],?dp[k][n-x])?>?max(dp[k-1][x],?dp[k][n-x-1])時x是最優解

思路②代碼如下：AC

class Solution {
public:int superEggDrop(int K, int N) {int dp[N+1];//dp[k-1][n]for(int i=0;i<=N;i++)dp[i]=i;int dp2[N+1];//dp[k][n]for(int k=2;k<=K;k++){int x=1;fill(dp2, dp2+N+1, 0);for(int n=1;n<=N;n++){while(x<n && (max(dp[x-1], dp2[n-x]) > max(dp[x], dp2[n-x-1])) )x++;dp2[n] = 1 + max(dp[x-1], dp2[n-x]);}for(int i=0;i<=N;i++) dp[i]=dp2[i];}return dp[N];}
};

雞蛋掉落實驗圖。思路①代碼如下：（超時）

class Solution {
public:int superEggDrop(int K, int N) {int dp[K+1][N+1];for(int k=1;k<=K;k++)for(int n=1;n<=N;n++)dp[k][n]=n;for(int k=2;k<=K;k++){for(int n=1;n<=N;n++){for(int i=1;i<n;i++){int tmp = 1 + max(dp[k-1][i-1], dp[k][n-i]);dp[k][n] = min(dp[k][n], tmp);}}	}return dp[K][N];}
};

?