思路：

题目中给到的信息：

第0层不会碎
某层没有碎，下面的必然不会碎；某层碎了，上面的必然碎
要求最坏情况

方法一：暴力递归（超时）

设count(n,k)计算的是n层楼时且有k个棋子，在最差的情况下需要仍的最少次数。

当k=0时，没有棋子，不用仍
当n=0时，棋子肯定不会碎，所以count(0, k)=0
当k=1时，只有1个棋子，只能从第1层楼开始尝试，每层都要试试：count(n,1)=n

三种特殊情况排除完，我们要看第1颗棋子仍的楼层，假设第1个棋子从第i层开始仍，那么有以下两种情况:

碎了。接下来就变成了剩下i-1层楼和K-1个棋子的子问题，所以总步数为 1+count(i-1, k-1)
没碎。没必要尝试第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。

class Solution {
public:
    int count(int n, int k){
        if(n == 0) 
            return 0;
        else if(k == 1)
            return n;//只有一颗棋子，需要仍n次
        int minval = 1000001;  //n,k最大为10^6
        for(int i=1; i <= n; i++){
            int temp = max(count(i-1, k-1), count(n-i, k));  //找最坏情况
            minval = min(minval, temp);
        }
        return minval+1;
    }
    int solve(int n, int k) {
        if(n < 1 || k < 1) //都为0，自然不需要仍棋子
            return 0;
        return count(n, k);
    }
};

复杂度分析

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

方法二：动态规划(超内存） 上面count函数调用了多次，事实上重复了很多时间，因此可以用一个二维矩阵来存储count中的值，也可以直接在矩阵中叠加上述公式将矩阵填满以得到结果。

class Solution {
public:
    int solve(int n, int k){
        if(n == 0) 
            return 0;
        else if(k == 1)
            return n;//只有一颗棋子，需要仍n次
        vector<vector<int> > dp(n + 1, vector<int>(k + 1)); //dp矩阵记录前一个方法里的返回值
        for(int i = 1; i < dp.size(); i++) {  //每行首初始化为该行号，代表只有一颗棋子时需要的次数
        	dp[i][1] = i;
        }
        for(int i = 1; i < dp.size(); i++) {
        	for(int j = 2; j <= k; j++) {
        		int minval =  1000001;  //n,k最大为10^6
        		for(int z = 1; z < i + 1; z++) {
                    int temp = max(dp[z-1][j-1], dp[i-z][j]); //利用动态规划直接相加，而非调用函数
        			minval = min(minval,temp);
        		}
        		dp[i][j] = minval + 1;
        	}
        }
        return dp[n][k];
    }
};

复杂度分析：

时间复杂度：O(n^2 * k)，最坏两个会循环到两次n（第三个for循环）
空间复杂度：O(nk)，dp矩阵大小

方法三：二分法扔棋子（一维动态规划） 性质：如果k充分大, 可以通过二分的方式扔棋子, 至多扔log2(n)+1就能确定, 因此k如果大于该值, 直接返回log2(n)+1即可 该性质可以减少大数时的运算时间。再：如果令dp[i][j] 表示i个棋子扔j次, 最多可以测多少层（注意与方法一count和方法二dp的不同）。那么当第i个棋子在最优的楼层扔下去时，与方法一的结果相同，知识用dp矩阵表示：

碎了。那么上面的楼层就不用测了, 下面能测的是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 至此，空间问题就解决了。详情可见图示：图片说明

class Solution {
public:
    int solve(int n, int k){
        if (n == 0) return 0;
        if (k == 1) return n;
        int b = log2(n) + 1; //如果k很大, 二分的扔即可
        if (k >= b) 
            return b;
        vector<int> dp(n, 1);// 设置初始值, 不管有几个棋子, 扔1次只能测1层
        int res = 1;  //除了0，至少要扔一次，可以设为res起点
        while(true) {
            res++; // 每一轮迭代, 次数增加1次
            //因为dp[i][j] 依赖的是左边和左上, 为了防止被覆盖, 需要倒着计算
            for (int i = k; i > 1; i--) {
                dp[i] = dp[i] + dp[i-1] + 1;
                if (dp[i] >= n) 
                    return res;
            }
            dp[1] = res; 
        }
    }   
};

复杂度分析：

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

题解 | #丢棋子问题#

思路：