887. Super Egg Drop

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

鸡蛋从第p层扔才会碎，现在有K个鸡蛋和N层，每步可以选择一个楼层往下扔，问至少需要多少步能找出p, p可以是N内任意一层。问题被鸡蛋数分成了K步，每步选择一个楼层扔，受限于楼层数。因此让dp[i][j]表示i个鸡蛋在j层楼至少需要的步数，从[0, j]遍历k扔，每次扔会碎或不碎，碎说明需要剩下i-1个蛋检测之前k-1层，没碎则是再i个蛋检测楼上的j-k层，因此 dp[i][j] = min(dp[i][j], 1 + max(dp[i - 1][k - 1] + dp[i][j-k]))。

然而这并不是最优解。最优解需要把最终所求encoding进状态，而把限制当作值。让dp[i][j]表示用i步和j个蛋最大能检测的层数。假设dp[i][j] == n, 走出最优一步到m层并拿出一个鸡蛋往下扔，会出现两种情况:

1. 碎了: 说明目标楼层一定在[0, m], m最大可能是用剩下的i-1步和j-1个鸡蛋能检测的最多的楼层，即dp[i - 1][j-1]。

2. 没碎: 说明目标楼层在[m + 1, n]，n最大可能是剩下的i-1步和j个鸡蛋最多能检测的层数dp[i-1][j]。

/*
 * @lc app=leetcode id=887 lang=cpp
 *
 * [887] Super Egg Drop
 *
 * https://leetcode.com/problems/super-egg-drop/description/
 *
 * algorithms
 * Hard (25.09%)
 * Likes:    461
 * Dislikes: 47
 * Total Accepted:    9.9K
 * Total Submissions: 38.4K
 * 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
 * 
 * 
 * 
 * 
 * 
 */

// @lc code=start
class Solution {
public:
    int superEggDrop(int K, int N) {
        vector<vector<int>> dp(N + 1, vector<int>(K + 1, 0));
        int i = 0;
        while (dp[i][K] < 0) {
            ++i;
            for (int j = 1; j <= K; ++j) {
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] + 1;
            }
        }
        return i; 
    }
};
// @lc code=end