LeetCode 1884. Egg Drop With 2 Eggs and N Floors

[Woodyiiiiiii]

DP:

1. 确保每个空间代表的意思
2. 递推公式

class Solution {
    
    public int twoEggDrop(int n) {
        
        int egg = 2;
        // dp[i][j] 表示第i+1个鸡蛋在j层楼确定f的最小次数
        int[][] dp = new int[egg][n + 1];
        
        // init
        for (int i = 0; i < egg; ++i) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        dp[0][0] = dp[1][0] = 0;
        
        // 因为只有一个鸡蛋，此时只能从下往上一个个试验
        for (int j = 1; j <= n; ++j) {
            dp[0][j] = j;
        }
        
        // k表示第一个鸡蛋在哪一层碎了，不管碎没碎所以先把操作次数+1
        // 接着如果碎了，就在下一块区域，此时取得是dp[0][k - 1]
        // 没碎，取得是上一块区域，为dp[1][j - k]
        // 因为保证都能取到，所以先求上述两者结果的Max
        // 接着求f
        for (int j = 1; j <= n; ++j) {
            for (int k = 1; k <= j; ++k) {
                dp[1][j] = Math.min(dp[1][j], Math.max(dp[0][k - 1] + 1, dp[1][j - k] + 1));
            }
        }
        
        return dp[1][n];
        
    }
    
}