题解 | 丢棋子问题

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最差情况下扔棋子的最小次数
     * @param n int整型 楼层数
     * @param k int整型 棋子数
     * @return int整型
     */
    public int solve (int n, int k) {
        // write code here
        if (n == 0) return 0;
        // 如果只有 1 个棋子，只能从 1 层一层层往上试，需要 n 次
        if (k == 1) return n;

        // 极致优化：如果棋子数非常多，其实这就变成了一个普通的二分查找问题。
        // 测试 n 层楼最多只需要 log2(n+1) 次。
        // 将 k 限制在一个合理的界限内，防止 k 过大导致申请不必要的超大数组。
        // int maxK = (int)(Math.log(n) / Math.log(2)) + 1;
        // k = Math.min(k, maxK);

        // dp[i] 表示有 i 个棋子，扔 m 次，最多能测多少层楼
        // 初始时 m = 0，所有 dp[i] 都是 0
        int[] dp = new int[k + 1];

        // m 记录尝试扔的次数
        int m = 0;

        // 只要当前 k 个棋子能测的楼层还不到 n，我们就再多扔一次
        while (dp[k] < n) {
            m++;
            // 滚动更新，从后往前遍历，防止前面的值被提前覆盖
            for (int i = k; i >= 1; i--) {
                dp[i] = dp[i] + dp[i - 1] + 1;
            }
        }

        return m;
    }
}