C++ 解法, 执行用时: 2ms, 内存消耗: 396KB, 提交时间: 2021-10-18

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];
        for(int &i:dp)
            i=1;
        for(int j=2;;j++)
        {
            for(int i=k;i>=2;i--)
            {
                dp[i]=dp[i]+dp[i-1]+1;
                if(dp[i]>=n)
                    return j;
            }
            dp[1]=j;
        }
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 408KB, 提交时间: 2022-02-10

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回最差情况下扔棋子的最小次数
     * @param n int整型 楼层数
     * @param k int整型 棋子数
     * @return int整型
     */
    int solve(int n, int k) {
        // write code here
        if(k == 1) return n;
        if(n == 0) return 0;
        if(k >= n) return log2(n) + 1;
        vector<int> dp(k+1, 1);
        
        int res = 1;
        while(true) {
            dp[1] = res;
            for(int g = k; g >= 2; g--) {
                dp[g] = dp[g] + dp[g-1];
                if(dp[g] >= n) {
                    return res;
                }
            }
            ++res;
        }
        return res;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 412KB, 提交时间: 2021-10-07

class Solution {
public:
    int solve(int n, int k) {
        if(n <= 1 || k == 1) return n; //层数小于等于1和棋子数等于1的情况
        int best = log2(n) + 1; //棋子足够条件下扔的最小次数
        if(k >= best) return best; //如果棋子数足够则返回最小次数
        int dp[k + 1]; //用来记录扔1~k个棋子能探测的最大层数
        for(int &i: dp) i = 1;
        dp[0]=0;//无论有几个棋子扔1次都只能探测一层
        for(int time = 2;;time++) { //从扔第2次开始（前面初始化dp数组时扔了第1次）
            for(int i = k; i >= 2; i--) { //从k个棋子开始刷新dp数组（倒过来刷新省去记录临时值的步骤）
                dp[i] = dp[i] + dp[i-1] + 1; //关键一步
                if(dp[i] >= n) return time; //如果探测层数大于n，则返回扔的次数
            }
            dp[1] = time; //1个棋子扔time次最多探测time层
        }
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 432KB, 提交时间: 2021-10-23

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];
        for(int &i:dp)
            i=1;
        for(int j=2;;j++){
            for(int i=k;i>=2;i--){
                dp[i] = dp[i]+dp[i-1]+1;
                if(dp[i]>=n)
                    return j;
            }
        dp[1]=j;
        }
           
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 468KB, 提交时间: 2021-09-02

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回最差情况下扔棋子的最小次数
     * @param n int整型 楼层数
     * @param k int整型 棋子数
     * @return int整型
     */
    int solve(int n, int k) {
        // write code here
        if(n<1) return 0;
        if(k==1) return n;
        int logtimes=log2(n)+1;
        if(k>=logtimes) return logtimes;
        vector<int>f(k+1,0);
        int cnt=0;
        while(f[k]<n){
            ++cnt;
            for(int i=k;i>0;--i)
                f[i]+=f[i-1]+1;
        }
        return cnt;
    }
};