【Q682】100层楼，两个玻璃球，求最少多少次测出能摔碎玻璃球的楼层

[shfshanyue]

给你两个一摸一样的球，这两个球如果从一定的高度掉到地上有可能就会摔碎，当然，如果在这个高度以下往下扔，怎么都不会碎，当然超过这个高度肯定就一定摔碎了。

现在已知这个恰巧摔碎高度范围在一层楼到100层楼之间。

如何用最少的试验次数，用这两个玻璃球测试出摔碎的楼高

[heretic-G]

假设最少次数是x次 那么第一个我们从哪里扔呢 ？从x 因为如果碎了 另一个球从1到x 正好就是x 如果没碎这时候我们第一个球第二次只剩x-1次 所以我们从x+x-1层扔 碎了从x+1到x + x-2 遍历 后面逻辑一样 减1去扔第一个球 没碎下次再减1 碎了从上一次的没碎的上一层遍历就好了

所以可以一共层数等于x + (x-1) + (x-2) + ... + 1 = 100

下面我们来解这个这个方程:

(x+1)*x/2 = 100

最终x向上取整,得到 x=14

因此，最优解在最坏情况的尝试次数是14次，第一次扔鸡蛋的楼层也是14层。

最后，让我们把第一个鸡蛋没碎的情况下，所尝试的楼层数完整列举出来：

14，27， 39， 50， 60， 69， 77， 84， 90， 95， 99， 100

[3N26]

function solution(n) {
    const dp = Array.from({ length: 2 }, () => new Array(n + 1).fill(0));
    for (let i = 1; i <= n; i++) {
        dp[0][i] = i;
        dp[1][i] = n;
        for (let j = 1; j <= i; j++) {
            dp[1][i] = Math.min(dp[1][i], Math.max(dp[0][j - 1], dp[1][i - j]) + 1);
        }
    }
    return dp[1][n - 1];
}