题解 | #丢棋子问题#

算法思想一：扔棋子方法凑够楼层（逆向思维）

解题思路：

1、初始化扔棋子的次数 t = 1

2、不断的给 t 赋值（增加），直到给出的 t 可以测出楼层 n； $while(calF(k, t) < n + 1)$ 其中 $calF(k, t)$ 为计算可测出最高楼层函数

1、当t = 1时，最多可以测出 2 层楼，即 t+1；当k = 1时，（假设 t = 2）则可以测出3层楼，即 t + 1

2、有 t 次机会，k 个棋子，使用一枚棋子一次机会

1、若棋子碎了，则t-1,k-1，递归 $calF(k - 1, t - 1)$

2、若棋子没碎，则 t-1, k不变，递归 $calF(k, t - 1)$

3、循环结束返回 t

图解：

代码展示：

C++版本

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回最差情况下扔棋子的最小次数
     * @param n int整型 楼层数
     * @param k int整型 棋子数
     * @return int整型
     */
    int calF(int k, int t) {
        if(t == 1 || k == 1) return t + 1;            // 如果只有一次尝试机会或者棋子只有一个，则只能确定尝试机会+1数量的楼层哪一层棋子会碎
        return calF(k - 1, t - 1) + calF(k, t - 1);   // 非上述情况则递归（棋子-1，则机会-1）和（棋子没碎，机会-1）
    }

    int solve(int n, int k) {
        // write code here
        int t = 1;
        while(calF(k, t) < n + 1) t++;                // 凑够n层的时候输出尝试的次数
        return t;
    }
};

复杂度分析

时间复杂度： $O(nt)$ ，t就是最终的结果，其实就是尝试t的过程，一直给t赋值+1然后凑到n层为止

空间复杂度： $O(t)$ ，递归栈空间的大小

算法思想二：暴力递归（超时）

解题思路：

设 $count(n,k)$ 计算的是n层楼时且有k个棋子，在最差的情况下需要仍的最少次数。
1、当k=0时，没有棋子，不用仍
2、当n=0时，棋子肯定不会碎，所以 $count(0, k)=0$
3、当k=1时，只有1个棋子，只能从第1层楼开始尝试，每层都要试试： $count(n,1)=n$
三种特殊情况排除完，我们要看第1颗棋子仍的楼层，假设第1个棋子从第i层开始仍，那么有以下两种情况:
1、碎了。接下来就变成了剩下i-1层楼和K-1个棋子的子问题，所以总步数为 $1+count(i-1, k-1)$
2、没碎。没必要尝试第i层及其以下的楼层了，接下来的问题就变成了还剩下n-i层和k个棋子，所以总步数为 $1+count(n-i, k)$
题目要求最坏情况，即取上述两种情况最大值再来加1（本次尝试）.
因此公式为： $count(n, k)=min{max{P(i-1, k-1), P(n-i, k)}}+1$ 。

复杂度分析

时间复杂度： $O(n!)$ ，每次问题规模只减少1, 循环n次

空间复杂度： $O(n)$ ，递归栈深度

根据复杂度分析可知，此方法超时，不推荐使用，只做了解即可

算法思想三：二分法（一维动态数组）

解题思路：

性质：如果k充分大, 可以通过二分的方式扔棋子, 至多扔 $log2(n)+1$ 就能确定, 因此k如果大于该值, 直接返回 $log2(n)+1$ 即可
该性质可以减少大数时的运算时间。
如果令 $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]元素只和上面元素和左上角元素有关系，于是可以压缩成一维数组： $dp[i] = dp[i] + dp[i-1] + 1$

代码展示：

JAVA版本

import java.util.*;
import java.lang.Math;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回最差情况下扔棋子的最小次数
     * @param n int整型 楼层数
     * @param k int整型 棋子数
     * @return int整型
     */
    public int solve (int n, int k) {
        // write code here
        if(n<1||k<1) return 0;
        if(k==1) return n;
        int h=(int)(Math.log(n)/Math.log(2))+1;
        // 如果k很大, 二分的扔即可
        if(k>h) return h;
        int[] dp=new int[k];
        // 除了0，至少要扔一次，可以设为res起点
        int res=1;
        while(true){
            int p=0;
            // dp[1] = 1
            for(int j=0;j<k;j++){
                // dp[j] += dp[j-1] + 1
                int temp=dp[j];
                dp[j]+=p+1;
                p=temp;
                if(dp[j]>=n) return res;
            }
            // 每一轮迭代 次数增加1
            res++;
        }
    }
}

复杂度分析

时间复杂度： $O(klgn)$ ，n被二分法转化成了lgn，一个for循环为 $O(k)$
空间复杂度： $O(n)$ ，辅助空间为一个一维数组