【每日算法Day 60】高楼扔鸡蛋问题优化

在昨天的高楼扔鸡蛋问题中，对于每个状态dp[i][j]我们都要线性搜索1~j的范围来确定最优的测试楼层，所以时间复杂度达到了O(K*N^2)，今天来尝试对其进行改进。

首先由于之前是线性搜索的，但是观察状态转移中的两个子状态：min(max(dp[i][j - x], dp[i - 1][x - 1])+1)，在当前状态下我们固定i和j，则可以发现一个单调增，一个单调减。则两者最大值的最小值出现在交汇处，可以尝试使用二分查找对每个状态下的线性查找进行优化。这时能将时间复杂度将为O(K*N*logN)。

我们还可以重新定义dp数组的含义与状态转移，dp[k][m]表示给定鸡蛋数k和最多允许扔鸡蛋的次数m时能够测试楼的最大层数。我们可以确定两点：

1. 无论你在哪层楼扔鸡蛋，鸡蛋只可能摔碎或者没摔碎，碎了的话就测楼下，没碎的话就测楼上。
2. 无论你上楼还是下楼，总的楼层数 = 楼上的楼层数 + 楼下的楼层数 + 1（当前这层楼）。

我们可以写出状态转移方程：

dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1

其中，dp[k][m - 1]表示鸡蛋没碎但允许扔鸡蛋的次数减一时可以向上测试的最大层数，dp[k - 1][m - 1]表示鸡蛋碎了，允许扔鸡蛋的次数也减一时可以向下测试的最大层数，1表示无论碎没碎当前层已经确定了。由于m不会超过N次（线性扫描N层）所以dp数组定为int[K + 1][N + 1]。

这样，我们要找的最终状态就不是dp[k][m]的值，而是dp[k][m]>=N时m的值。

public int superEggDrop2(int K, int N) {
    //dp[k][m] = n
    //当前有 k 个鸡蛋，可以尝试扔 m 次鸡蛋
    //这个状态下，最坏情况下最多能确切测试一栋 n 层的楼
    int[][]dp = new int[K + 1][N + 1];

    for (int j = 1; j <= N; j++) {
        dp[1][j] = j;
    }
    for (int i = 1; i <= K; i++) {
        dp[i][1] = 1;
        dp[i][0] = 0;
    }
    int m = 0;
    while (dp[K][m] < N) {
        m++;
        for (int k = 1; k <= K; k++)
            dp[k][m] = dp[k][m - 1] + dp[k - 1][m - 1] + 1;
    }
    return m;
}