题解 | #丢棋子问题#

public class Solution {

    public int solve (int n, int k) {
        if(k == 1) {
            return n;
        }
        if(n == 0) {
            return 0;
        }
        // 相当于对最高楼层 n 进行二分查找，h相当于log2(n) + 1
        int h = (int)(Math.log(n) / Math.log(2))+1;
        // 如果k很大, 二分的扔即可，只是一种特殊情况
        if(k > h) {
            return h;
        }
        // dp数组定义：确定当前的棋子个数k，能够确定的最高楼层数h
        int[] dp = new int[k];
        // base case：没有棋子，最多测0层
        dp[0] = 0;
        // base case：只有一个棋子，最坏情况下最多只能测一层楼
        dp[1] = 1;
        // 统计扔的次数
        int res = 1;
        while(true){
            // dp_i_1相当于dp[i-1]
            int dp_i_1 = 0;
            // 状态压缩后:
            // dp[i] = dp[i] + dp[i-1] + 1
            // 因为dp[i][j] 依赖的是左边和左上, 为了防止覆盖, 需要倒着计算
            for(int i = 0; i < k; i++){
                int temp = dp[i];
                // 相当于dp[i] = dp[i] + dp[i-1] + 1, dp_i_1相当于dp[i-1]
                dp[i] += dp_i_1 + 1;
                // 保存作为下一次的dp[i-1]
                dp_i_1 = temp;
                // 能够确定到最高层 n, 返回结果
                if(dp[i] >= n) {
                    return res;
                }
            }
            // 每一轮迭代 次数增加1，相当于确定最高楼层n允许扔的次数
            res++;
        }
    }
}