[数据结构与算法] 经典算法题：丢棋子问题或者丢玻璃球问题

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 经典算法题：丢棋子问题或者丢玻璃球问题 -> 正文阅读

[数据结构与算法]经典算法题：丢棋子问题或者丢玻璃球问题

问题描述

一座大楼有 n+1 层，地面算作第0层，最高的一层为第 n 层。已知棋子从第0层掉落肯定不会摔碎，从第 i 层掉落可能会摔碎，也可能不会摔碎。

给定整数 n 作为楼层数，再给定整数 k 作为棋子数，返回如果想找到棋子不会摔碎的最高层数，即使在最差的情况下扔的最小次数。一次只能扔一个棋子。

数据范围：?1≤i≤n,k≤106

要求：空间复杂度?O(k)，时间复杂度?O(km) (m是最终返回的结果)

示例1

输入：10,1

返回值：10

说明：因为只有1棵棋子，所以不得不从第1层开始一直试到第10层，在最差的情况下，即第10层是不会摔坏的最高层，最少也要扔10次

示例2

输入：3,2

返回值：2

说明：先在2层扔1棵棋子，如果碎了，试第1层，如果没碎，试第3层

示例3

输入：105,2

返回值：14

说明：

第一个棋子先在14层扔，碎了则用仅存的一个棋子试1~13层
若没碎，第一个棋子继续在27层扔，碎了则用仅存的一个棋子试15~26层
若没碎，第一个棋子继续在39层扔，碎了则用仅存的一个棋子试28~38层
若没碎，第一个棋子继续在50层扔，碎了则用仅存的一个棋子试40~49层
若没碎，第一个棋子继续在60层扔，碎了则用仅存的一个棋子试51~59层
若没碎，第一个棋子继续在69层扔，碎了则用仅存的一个棋子试61~68层
若没碎，第一个棋子继续在77层扔，碎了则用仅存的一个棋子试70~76层
若没碎，第一个棋子继续在84层扔，碎了则用仅存的一个棋子试78~83层
若没碎，第一个棋子继续在90层扔，碎了则用仅存的一个棋子试85~89层
若没碎，第一个棋子继续在95层扔，碎了则用仅存的一个棋子试91~94层
若没碎，第一个棋子继续在99层扔，碎了则用仅存的一个棋子试96~98层
若没碎，第一个棋子继续在102层扔，碎了则用仅存的一个棋子试100、101层
若没碎，第一个棋子继续在104层扔，碎了则用仅存的一个棋子试103层
若没碎，第一个棋子继续在105层扔，若到这一步还没碎，那么105便是结果

问题地址：丢棋子问题_牛客题霸_牛客网

解法一：动态规划正向求解

设n为楼层数，k为棋子数， $p(n,k)$ 表示n层楼k个棋子最优解；

如果n=0，0层楼不会碎，也就不容扔，则次数p=0;

如果k=1，只有一个棋子，那么只能从1到n尝试，则 $p(n,k) = n$

其他情况k > 1, n > 0

那么可能的情况就是从 $i=1$ 到 $n$ 尝试，得到其中的最优解（最小值）；

在扔i层楼的时候可能碰到的情况有二：

1、碎了，那么还需要尝试的次数是 $p(i-1,k-1)$ ；

2、没碎，那么需要尝试的次数是 $p(n-i,k)$ ；

考虑这两者中比较糟糕的情况那么应该取 $max(p(i-1,k-1),p(n-i,k))$ ；

最后的公式 $P(n, k)=min(max(P(i-1, k-1), P(n-i, k))(for 1<=i<=n))+1$

时间复杂度 $O(n^2k)$

复杂度太高，无法实际应用！

    public int solutionTwo(int N, int K){
        if ( N<1 || K<1 ) 
            return 0;
        if ( K == 1 ) return N;
        int[][] dp = new int[N+1][K+1];
        for(int i=1; i<dp.length; ++i) {
        	dp[i][1] = i;
        }
        for(int i=1; i<dp.length; ++i) {
        	for(int j=2; j<=K; ++j) {
        		int min = Integer.MAX_VALUE;
        		for(int k=1; k<i+1; ++k) {
        			min = Math.min(min, Math.max(dp[k-1][j-1], dp[i-k][j]));
        		}
        		dp[i][j] = min + 1;
        	}
        }
        return dp[N][K];
    }

?解法来源：丢棋子问题 ——(动态规划) - willwuss - 博客园

解法二：?动态规划反向求解

考虑进行如下问题转换：

设k为棋子数，n为扔的次数，那么p(k,n)表示k个棋子扔n次最多能取得的楼层数；

这两个问题可以等效，默认每次都是在最优的楼层扔的，而我们不用考虑哪一层最优；

如果n=1，扔一次那么永远只能得到一层楼的结果；

如果k=1，只有一个棋子，那么最后楼层数也就是扔的次数；

考虑其他情况n>1, k >1

如果在某层x扔的时候就有两种情况：

碎了：那么就只有k-1个棋子，次数n-1，得到楼层数 $p(k-1,n-1)$ ；

没碎：那么扔然剩下k个棋子，次数n-1，得到楼层数 $p(k,n-1)$ ；

计算扔的层数递推公式： $p(k,n) = p(k-1,n-1) + p(k,n-1) + 1$ （包含某层x）?；

还有一种情况是棋子数量足够的时候可以用二分法，那么次数是 $log_2N$ +1 N为目标楼层数

时间复杂度 $O(Km)$ ?k为棋子数 m为扔的次数

    int solve(int n, int k) {
        // write code here
        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; //无论有几个棋子扔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层
        }
    }

下面的表格表示这样的迭代过程，从n=1到最后的答案m，需要的数组大小为棋子数k；

每行数据的关系满足上面的公式： $p(k,n) = p(k-1,n-1) + p(k,n-1) + 1$

注意每列第一个元素要随着次数n的增加而增加！