题解 | #丢棋子问题#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回最差情况下扔棋子的最小次数
     * @param n int整型 楼层数
     * @param k int整型 棋子数
     * @return int整型
     */
    int solve(int n, int k) {
        // write code here
        if(n <= 1 || k == 1) return n; 
        int best = log2(n) + 1; // 优化，最优情况下，需要的最少次数
        if(k > best) return best;
        int dp[k + 1]; // 用来记录1-k个棋子能探测的最大层数
        for(int &i : dp) i = 1; // 扔一次只能探测一层
        for(int time = 2; ; time++) { // time指扔了几次
            int temp = dp[1]; // 保存前一次扔棋子结果
            for(int i= 2; i <= k; i++) {
                int previous = temp;
                temp = dp[i];
                dp[i] = dp[i] + previous + 1;
                if(dp[i] >= n) 
                    return time;
            }
            dp[1] = time;
        }
    }
};