题解 | #丢棋子问题#

nc87. 丢棋子问题

1. 暴力搜索 (不合要求, TLE)

令f(n, k) 表示n层楼, k个棋子, 在最差情况下的最少实验次数.

f(n,k) 有下列性质:

若n=0, 地板上肯定不碎, 不需要任何实验, 故f=0.
若k=1, 只有1个棋子必须逐层操作,在最差情况下第n层楼才摔碎, 需要n次实验. 故f=n.
其他情况, 考虑第一枚棋子是在第j层扔下去的, 有两种情况:

碎了, 说明第j层以上必定还碎, 所以剩下了k-1枚棋子和j-1层楼, 剩下的实验次数为f(j-1, k-1), 且进行了一次实验.
没碎, 说明j层及j层以下必定还不碎, 所以剩下了k枚棋子(注意!!!这一枚棋子还是能用的!!!) 和n-j层楼, 剩下的实验次数为f(n-j, k), 且进行了一次实验.

而我们不知道第j层会不会碎, 题目要求的是最差情况下的次数, 所以要考虑最坏情况, 也就是以上两种情况的最大值, 且j的取值是不确定的, 取值范围是[1, n]. 因此, 我们要枚举j, 计算j的所有取值中最小的那一个, 才能代表最少实验次数.

实现: (不合要求, 会tle)

class Solution {
public:
    int solve(int n, int k) {
        if (n == 0) return 0;
        if (k == 1) return n;

        int res = INT_MAX;
        for (int j = 1; j <= n; j++) {
            res = min(res, 1+max(solve(j-1, k-1), solve(n-j, k)));
        }
        return res;
    }
};

时间复杂度: O(n!), 因为每次问题规模只减少1, 却要循环n次, 得出关系式T(n)=nT(n-1), 故是阶乘复杂度.
空间复杂度: O(1), 没有额外空间.

2. 动态规划(不合要求, TLE)

根据上面的关系式可知, 问题具有动态规划的转移性质, 因此可以通过动态规划实现.

转移关系定义: dp[n][k] 表示n层楼, k个棋子, 在最差情况下的最少实验次数.
初值: dp[0][k] = 0, dp[i][1] = i
最终答案: dp[n][k].
转移方程: dp[i][j] = min(1+max(dp[k-1][j-1], dp[i-k][j]))

实现: (不合要求, sf)

class Solution {
public:

    // 转移方程: `dp[i][j] = min(1+max(dp[k-1][j-1], dp[i-k][j]))`
    static const int N = 1e6 + 5;
    int dp[N][N];

    int solve(int n, int k) {
        if (n == 0) return 0;
        if (k == 1) return n;

        for (int i = 1; i < N; i++) dp[i][1] = i;

        for (int i = 1; i < N; i++) {
            for (int j = 2; j <= k; j++) {
                dp[i][j] = INT_MAX;
                for (int p = 1; p <= i; p++) {
                    dp[i][j] = min(dp[i][j], 1+max(dp[p-1][j-1], dp[i-p][j]));
                }
            }
        }
        return dp[n][k];
    }
};

时间复杂度: O(n^2*k), 题目中nk都是1e6, 所以不合要求.
空间复杂度: O(nk), 考虑转移式中j这个维度只跟j-1有关, 故可以压缩掉一维, 空间复杂度最多可以做到O(n).

3. 反向思维的动态规划

我们换一种思路. 方法二的dp方程的目标值是基于最少实验次数, 我们反向思考之, dp方程将会变得很简单.

令dp[i][j] 表示i个棋子扔j次, 最多能测多少层. 考虑第i个棋子在最优的楼层扔下去, 有两种情况:

碎了, 那么上面就不用测了, 下面能测的是dp[i-1][j-1]层
没碎, 那么下面就不用测了, 上面能测dp[i][j-1]层
第i个棋子扔掉的那一层也能测.

综上, 考虑最差的情形, 可以得到转移式:

dp[i][j] = dp[i-1][j-1] + dp[i][j-1] + 1

显然dp[i][j]是单调递增的, 那么, 我们要求的答案就是, 在i不超过k的情况下, 使得dp[i][j] >= n的最小的j.

根据以上分析, 我们的dp关系可以总结如下:

转移关系定义: dp[i][j] 表示i个棋子扔j次, 最多能测多少层.
初值: dp[i][1] = 1, 不管有几个棋子, 扔1次只能测1层.
最终答案: i不超过k时候, 使得dp[i][j] >= n的最小的j.
转移方程: dp[i][j] = dp[i-1][j-1] + dp[i][j-1] + 1

这里有一个性质, 如果k充分大, 我们可以通过二分的方式, 至多扔log2(n)+1就能确定, 因此k如果大于该值, 直接返回log2(n)+1即可.

另外要注意的是，我们发现, dp[i][j]只和上面元素和左上面元素有关系，故可以压缩一维，并且需要逆向计算。
这个逻辑可以用图描述如下
图片说明

用粉色表示dp[i][j], 黄色表示dp[i-1][j], 在计算dp[i][j]的时候，先从右侧开始计算，算到i的时候，一开始dp[i]处为黄色，存储的是上一次迭代的结果dp[i][j-1], i-1处也为黄色，因此dp[i] = dp[i] + dp[i-1] + 1就等价于dp[i][j] = dp[i-1][j-1] + dp[i][j-1] + 1. 如果反了，那么算到i的时候， i-1处就变成了粉色，转移方程就相当于dp[i][j] = dp[i-1][j] + dp[i][j-1] + 1, 导致wa。

类似可以参考01背包和完全背包中代码逻辑的区别，在此不再赘述。
实现代码:

class Solution {
public:
    // dp[i][j] = dp[i-1][j-1] + dp[i][j-1] + 1
    static const int N = 1e6+5;
    int dp[N];

    int solve(int n, int k) {
        if (n == 0) return 0;
        if (k == 1) return n;

        // 优化性质, 如果k充分大, 二分的扔即可
        int b = log2(n) + 1; 
        if (k >= b) return b;

        // 初始值, 不管有几个棋子, 扔1次只能测1层
        for (int i = 0; i < N; i++) dp[i] = 1;

        // 最少也得扔1次
        int res = 1;
        while(1) {
            res++; // 每一轮迭代, j增加1次

            // 转移方程:
            // dp[i][j] = dp[i-1][j-1] + dp[i][j-1] + 1
            // 压缩后:
            // dp[i] = dp[i] + dp[i-1] + 1
            // 因为dp[i][j] 依赖的是左边和左上, 为了防止覆盖, 需要倒着计算
            // 参考01背包问题的解题思路
            for (int i = k; i >= 2; i--) {
                dp[i] = dp[i] + dp[i-1] + 1;
                if (dp[i] >= n) return res;
            }

            dp[1] = res; // dp[1][j] = j
        }
    }
};

时间复杂度: O(klogn). 代码中的外层while最多迭代logn轮, 否则可以使用二分扔棋子的方式解决, 内层循环是k次, 故总的时间复杂度最坏为O(klogn).
空间复杂度: O(n), 开了一个长度为n 的dp数组.