首页 > 试题广场 >

丢棋子问题

[编程题]丢棋子问题
  • 热度指数:18920 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解

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

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

数据范围: 
要求:空间复杂度 ,时间复杂度 (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便是结果

备注:

python解法
思想:dp[i][j]=dp[i][j-1]+ dp[i-1][j-1]+1
dp[i][j-1]:当前棋子没有碎
dp[i-1][j-1]:当前棋子碎了
1:当前棋子占用1次

from functools import lru_cache
class Solution:
    def solve(self , n , k ):
        # write code here
        @lru_cache()
        def fun(qi, n):
            if qi == 1: return n
            if n == 1: return 1
            return fun(qi,n-1) + fun(qi-1,n-1) + 1
        res = 1
        while fun(k, res) < n:
            res += 1
        return res
发表于 2021-03-25 15:05:01 回复(0)
i个棋子扔j次,假设可以搞定 dp[i][j] 层高的楼
则 dp[i][j]=1+dp[i-1][j-1]+dp[i][j-1]
即在中间一层扔一个棋子,碎了,往下可以搞定dp[i-1][j-1],没碎往上搞定dp[i][j-1]
1个棋子扔N次,可以搞定N层楼
N个旗子只能扔一次,只能搞定一层楼。
如果棋子不够用,i为棋子数目,j为扔的次数

class Solution {
public:
    int solve(int n, int k) {
        
        if( n<=1 ) return n; 
        if(k==1) return n;
        // 棋子完全够用的情况下,那么最多要best个棋子和best步就可以搞定n层楼
        int best=log2f(n)+1;
        if(k>=best) return best;
        
        vector< vector<int> > dp;
        
        for(int i=0;i<=k;i++){
            vector<int> temp;
            if(i==0){
                dp.push_back(temp);
                continue;
            }
            if(i==1){
                for(int j=0;j<=n;j++) temp.push_back(j);
                dp.push_back(temp);
                continue;
            }
            temp.push_back(0);
            temp.push_back(1);
            for(int j=2;j<=n;j++){
                ////int dpij=1+dp[i-1][j-1]+dp[i][j-1];
                int dpij=1+dp[i-1][j-1]+temp[j-1];
                temp.push_back(dpij);
                if(i==k && dpij>=n ) return j;
                if(dpij>=n) break;
            }
            dp.push_back(temp);
        }
    }
};



编辑于 2021-06-19 11:02:59 回复(0)
你管这叫中等题?
发表于 2021-05-21 10:37:37 回复(1)
难道只有我一个人只会暴力动态规划时间超时,其他方法看的头超疼
发表于 2020-09-16 01:06:33 回复(1)
题都看不懂
发表于 2021-08-05 20:29:30 回复(0)
读了半天没读明白 ,啥意思啊这是?
发表于 2020-10-16 21:15:55 回复(9)
此题转换思想,先求出k个棋子times步下能够辨别的最大n值,选择动态规划,dp[i][j]为i个棋子下j次能够辨别的最大n值,则有:dp[i][j]=dp[i][j-1]+ dp[i-1][j-1]+1;
这里为了省空间,就没有dp矩阵了,只有last矩阵和 tmp矩阵。last[i]矩阵代表j-1步下的i棋子辨别最大数。 tmp矩阵代表j步下的i棋子辨别最大数。
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 返回最差情况下扔棋子的最小次数
     * @param n int整型 楼层数
     * @param k int整型 棋子数
     * @return int整型
     */
    
int solve(int n, int k) {
	// write code here
	int maxn = 0, times = 1;
	vector<int> tmp(k + 1, 0);
	vector<int> last(k + 1, 0);
	while (maxn < n) {
		for (int num = 1; num <= k; num++) {
            if (times ==1)
				tmp[num] = 1;
			else if (num == 1)
				tmp[num] = times;
			else
				tmp[num] = last[num - 1] + last[num] + 1;
		}
		maxn = tmp.back();
		last = tmp;
		times++;
	}
	return times - 1;
}
};


编辑于 2020-10-20 14:47:49 回复(0)
解题思路:由初始的二维DP进行优化,二维DP状态转移方程:dp[i][j]=Math.min(min,Math.max(dp[i-1][k-1],dp[n-i][k])+1),这样占用空间很大,根据题意中最后一个例子,找到最优解的规律,可以进一步优化成一维DP,状态转移方程:dp[j]+=dp[j-1]+1,当dp[j]大于等于n时,意味着此时丢棋子次数达到最优解
import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 返回最差情况下扔棋子的最小次数
     * @param n int整型 楼层数
     * @param k int整型 棋子数
     * @return int整型
     */
    public int solve (int n, int k) {
        // 状态转移方程:dp[i][j]=dp[i][j-1]+dp[i-1][j-1]+1
        if(k==1) return n;
        int h=(int)(Math.log(n)/Math.log(2))+1;
        if(k>h) return h;
        int[] dp=new int[k];
        int i=1;
        while(true){
            int p=0;
            for(int j=0;j<k;j++){
                int temp=dp[j];
                dp[j]+=p+1;
                p=temp;
                if(dp[j]>=n) return i;
            }
            i++;
        }
    }
}


发表于 2021-03-23 09:50:26 回复(0)
Python解
转载一下写的比较好的一个博客https://www.cnblogs.com/willwuss/p/12256475.html
简单说以下自己看懂的三种方法
1.暴力递归(不建议)
设函数F(n,k)返回的是给定n,k所返回的最小试验次数。
Case1:当n=0时,根据已知不用实验即可得到结果,故F(0,k)=0
Case2:当k=1且n>0时,实际上就是示例1的情况,从第一层开始尝试,最差情况一直到最后一层故F(n,k)=n,n>0。
Case3:对于一般化情况进行分析,第一个棋子是从第i层扔的,此时会有两种情况:
        1.棋子碎了,总数量-1变成k-1,并且从第i层下面开始搜索,F(i,k) = F(i-1,k-1);
        2.棋子没碎,总数量仍为k,从第i层上面开始扔,F(n-i,k)
        为了得到最差情况,我们应该选两者中较大的情况即max{F(i-1,k-1),F(n-i,k)}+1,+1表示在第i层扔了一次,由于i的取值为[1,n],因此F(n,k) = min{max{F(i-1,k-1),F(n-i,k)} (1)}+1。(不建议使用  第三个样例在Pycharm中会崩溃)  时间复杂度为O(n!)
class Solution:
    def solve(self,n ,k ):
        if n<1&nbs***bsp;k<1:
            return 0
        return self.helper(n,k)

    def helper(self,n,k):
        if n==0:return 0
        if k==1:return n
        mins = 0x7fffffff

        for i in range(1,n):
            mins = min(mins,max(self.helper(i-1,k-1),self.helper(n-i,k)))

        return mins+1
2.动态规划
在上述过程中,不难发现整个过程中的各个情况实际上是存在递推式的,我们不妨建立矩阵dp,维数为{n+1,k+1},矩阵中的每个元素dp[i][j]都表示F(i,j)。初始位置正如1中所分析的Case1和Case2,我们用n=3,k=2为例,初始条件,tbd表示待定
对于其余位置,我们建立递推式即dp[n][k] = min{max{dp[i-1][k-1],dp[n-i][k]}+1
class Solution1:
    def solve(self , n , k ):
        # write code here
        if n<1&nbs***bsp;k<1:
            return 0
        if k==1:
            return n
        dp = [[0]*(k+1) for i in range(n+1)]
        for i in range(1,n+1):
            dp[i][1] = i
        for i in range(1,k+1):
            dp[1][i] = 1

        for i in range(2,n+1):
            for j in range(2,k+1):
                mins = 0x7fffffff
                for m in range(1,i+1):
                    mins = min(mins,max(dp[m-1][j-1],dp[i-m][j]))
                dp[i][j] = mins+1
        return dp
3.最优解法
        最优解比一上各种方法都快。首先我们换个角度来看这个问题,以上各种方法解决问题是N层楼有K个棋子最少仍多少次。现在反过来看K个棋子如果可以仍M次,最多可以解决多少楼层这个问题。根据上文实现的函数可以生成下表。在这个表中记作map, map[i][j]的意义为i个棋子仍j次最多搞定的楼层数

        通过研究map表发现,第一排的值从左到有一次为1,2,3...,第一纵列都为0, 初次之外的其他位置(i, j),都有 map[i][j] == map[i][j-1] + map[i-1][j-1] + 1.
将设i个棋子仍j次最多搞定m层楼,“搞定最多”说明每次仍的位置都是最优的且在棋子肯定够用的情况下,若第1个棋子仍在a层楼是最优的。
1. 如果第1个棋子以碎,那么就向下,看i-1个棋子扔j-1次最多搞定多少层楼;
2. 如果第1个棋子没碎,那么就向上,看i个棋子扔j-1次最多搞定多少层楼;
3. a层楼本身也是被搞定的1层;
        1、2、3的总楼数就是i个棋子扔j次最多搞定的楼数,map表的生成过程极为简单,同时数值增长的极快。原始问题可以通过map表得到很好的解决。
        例如,想求5个棋子搞定200层楼最少扔多少次的问题,注意到第5行第8列对应的值为218,是第5行的所有值中第一次超过200的值,则可以知道5个棋子搞定200层楼最少扔8次。同时在map表中其实9列10列的值也完全可以不需要计算,因为算到第8列就已经搞定,那么时间复杂度得到进一步的优化。另外还有一个特别重要的优化,我们知道N层楼完全用二分的方式扔logN+1次就直接可以确定哪层楼是会碎的最低层楼,所以当棋子数大于logN+1时,我们就可以返回logN+1.
        如果棋子数位K,楼数位N, 最终的结果位M次,那么最优解的时间复杂度为O(KxM), 在棋子数大于logN+1时,时间复杂度为O(logN). 在只要1个棋子的时候, KxM等于N, 在其他情况下 KxM要比N得多
import math
class Solution:
    def solve(self , n , k ):
        if n<1&nbs***bsp;k<1:
            return 0
        if k==1:
            return n
        bsTimes = math.log2(n)+1

        if k>bsTimes:return bsTimes

        dp = [0]*k
        res = 0
        while True:
            res = res+1
            previous = 0
            for i in range(len(dp)):
                tmp = dp[i]
                dp[i] = dp[i]+previous+1
                previous = tmp
                if (dp[i]>=n):
                    return res


发表于 2020-12-17 16:29:09 回复(2)
我直接亚麻呆住
发表于 2023-08-22 22:47:17 回复(0)
这个题目的描述就有逻辑漏洞,“最差的情况”,什么叫“最差的情况”?就是倒霉运倒到家了,扔个一百万次都TM是碎的,一共100层楼,每一层楼都是碎,这就是最倒霉的情况,那你就需要试无穷次,而且无穷次也的不出来结果,只能得出来“不存在这样的楼层不会碎”的结果,你得说至少存在一个楼层不会碎才行
发表于 2023-08-01 14:59:47 回复(1)

这是根据各位大神的解法,拼凑出来的一种我可以看懂,而且可以通过的解法(动态规划+二分优化+空间优化)

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 返回最差情况下扔棋子的最小次数
     * @param n int整型 楼层数
     * @param k int整型 棋子数
     * @return int整型
     */
    public int solve (int n, int k) {
        int[] pre = new int[n + 1];
        int[] dp = new int[n + 1];
        int res = (int) (Math.log(n) / Math.log(2)) + 1;
        if (res <= k) return res;
        for (int i = 1; i <= n; i++) {
            dp[i] = i;
        }
        for (int i = 2; i <= k; i++) {
            pre = dp;
            dp = new int[n + 1];
            for (int j = 1; j <= n; j++) {
                int l = 0;
                int r = j;
                while (l < r) {
                    int mid = (l + r) / 2;
                    int idx = j - 1 - mid;
                    if (r - l <= 1) {
                        dp[j] = 1 + Math.max(dp[l], pre[r]);
                        break;
                    }
                    if (pre[mid] == dp[idx]) {
                        dp[j] = dp[idx] + 1;
                        break;
                    }
                    if (pre[mid] > dp[idx]) {
                        r = mid;
                    } else {
                        l = mid;
                    }
                }
            }
        }
        return dp[n];
    }
}
发表于 2022-09-25 20:33:26 回复(0)
# -*- coding: utf-8 -*-

import math


#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
# 返回最差情况下扔棋子的最小次数
# @param n int整型 楼层数
# @param k int整型 棋子数
# @return int整型
#
class Solution1:
    """
    题目:
        https://www.nowcoder.com/practice/d1418aaa147a4cb394c3c3efc4302266?tpId=196&tqId=37178&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D2%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=2&tags=&title=
    算法1:
         # 超时 !!!!!

        设dp[i][j]表示i层楼,j个棋子,在最差情况下的最少试验次数
        初始化:
            dp[0][0] = 0
        状态转移方程:
            dp[i][0] = 0 # i层楼,0个棋子,无须试验
            dp[i][1] = i # i层楼,1个棋子,试验 i 次
            dp[0][j] = 0 # 0层楼,j个棋子,无须试验
            dp[1][j] = 1 # 1层楼,j个棋子,试验 1 次
            dp[i][j] = min(1 + max(dp[k - 1][j - 1], dp[i - k][j])), 1 <= k <= i,这里选取从第k层扔下一个棋子,如果碎了,那么大于k的楼层必然会碎,问题变为 k - 1 层楼,j - 1个棋子进行试验;如果没碎,那么小于k的楼层必然不碎,问题转变为i - k层楼,j个棋子进行试验。另外需要注意的是,没经过一次试验,次数+1。同时我们取得是最少试验次数。
        返回值:
            dp[n][k]
    复杂度:
        时间复杂度:O(n^2 * k)
        空间复杂度:O(n * k)
    """

    def solve(self, n, k):
        # write code here
        dp = [[10 ** 6] * (k + 1) for _ in range(n + 1)]

        for i in range(1, n + 1):
            dp[i][1] = i
        for j in range(1, k + 1):
            dp[1][j] = 1

        for i in range(2, n + 1):
            for j in range(2, k + 1):
                for l in range(1, i + 1):
                    dp[i][j] = min(dp[i][j], 1 + max(dp[l - 1][j - 1], dp[i - l][j]))

        return dp[n][k]


class Solution:
    """
    参考:
        大神:棒棒糖🍭201906101800876
    算法:
        设dp[i][j]表示i个棋子扔j次, 最多能测多少层。考虑第i个棋子在最优的楼层扔下去, 有两种情况:
            a. 碎了, 那么上面就不用测了, 下面能测的是dp[i-1][j-1]层
            b. 没碎, 那么下面就不用测了, 上面能测dp[i][j-1]层
            c. 第i个棋子扔掉的那一层也能测.
        综上,状态转移方程:
            dp[i][j] = dp[i-1][j-1] + dp[i][j-1] + 1
        显然dp[i][j]是单调递增的, 那么我们要求的答案就是在i不超过k的情况下, 使得dp[i][j] >= n的最小的j。
        不难发现,dp[i][j]只和上面元素和左上面元素有关系, 故可以压缩一维,并且需要逆向计算。在计算dp[i][j]的时候,先从右侧开始计算,算到i的时候,一开始dp[i]处为黄色,存储的是上一次迭代的结果dp[i][j-1], i-1处也为黄色,因此dp[i] = dp[i] + dp[i-1] + 1就等价于dp[i][j] = dp[i-1][j-1] + dp[i][j-1] + 1。如果反了,那么算到i的时候, i-1处就变成了粉色,转移方程就相当于dp[i][j] = dp[i-1][j] + dp[i][j-1] + 1, 导致wa
    复杂度:
        时间复杂度:O(klogn)
        空间复杂度:O(k)
    """

    def solve(self, n, k):
        # write code here
        if n == 0:
            return 0
        if k == 1:
            return n

        b = int(math.log10(n) / math.log10(2)) + 1  # 优化性质, 如果k充分大, 二分的扔即可,python27没有math.log2(x), 数学替代:log2(n) = log10(n)/log10(2)
        if k >= b:
            return b

        dp = [1] * (k + 1)  # 初始值, 不管有几个棋子, 扔1次只能测1层
        res = 1  # 最少扔1次

        while True:
            res += 1  # 每一轮迭代, j增加1次
            for i in range(k, 1, -1):
                dp[i] = dp[i] + dp[i - 1] + 1
                if dp[i] >= n:  # 当前尝试的楼层到达n,找到解
                    return res
            dp[1] = res  # dp[1][j] = j,1个棋子扔j次,测得楼层为j


if __name__ == '__main__':
    s = Solution()

    # n, k = 10, 1

    # n, k = 3, 2

    # n, k = 105, 2

    # n, k = 874520, 7

    n, k = 1, 1000000

    res = s.solve(n, k)

    print res

发表于 2022-07-06 22:03:42 回复(0)
四边形不等式都超时,真的离谱离到姥姥家。
非得用那个最神奇的dp含义定义表--i个棋子丢j次最多能解决几层楼问题。
能过的代码:
    public int solve (int n, int k) {
        return bestWay(n,k);
        // write code here
    }
    public static int bestWay(int remain,int k){//最吊的方法
        int[] dp = new int[k + 1];
        int step = 1;
        while(true){
            for(int i = k;i > 0;i--){
                dp[i] = dp[i-1] + dp[i] + 1;
            }
            if(dp[k] >= remain){
                return step;
            }
            step++;
        }
    }
令人自豪四边形不等式:
    public int dpWay(int n,int sum){//四边形不等式
        int[][] dp = new int[n+1][sum+1];
        int[][] s = new int[n+1][sum+1];
        for(int i = 0;i < dp.length;i++){
            s[i][1] = 1;
            dp[i][1] = i;
        }
        for(int i = 1;i < dp[0].length;i++){
            dp[1][i] = 1;
            s[1][i] = 1;
        }
        for(int i = 2;i < dp.length;i++){
            for(int j = sum;j >= 2;j--){
                int low = s[i-1][j];
                int up = j < sum ? s[i][j+1] : i;
                dp[i][j] = i;
                s[i][j] = i;
                for(int k = low;k <= up;k++){
                    int max = Math.max(dp[k-1][j-1],dp[i-k][j]) + 1;
                    if(max < dp[i][j]){
                        dp[i][j] = max;
                        s[i][j] = k;
                    }
                }
            }
        }
        return dp[n][sum];
    }



发表于 2022-04-28 18:31:28 回复(0)
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 返回最差情况下扔棋子的最小次数
     * @param n int整型 楼层数
     * @param k int整型 棋子数
     * @return int整型
     */
    
    public int solve (int n, int k) {
        // write code here
        int testCount = 1;
        while(t(testCount,k) < n){
            ++testCount;
        }
        return testCount;
    }
    
    
    //扔的次数可以确定多少楼层
    private int t(int testCount, int k){
        if(testCount == 1 || k == 1){
            return testCount;
        }

        return t(testCount-1,k) + 1 + t(testCount-1, k-1);
    }
    
}

发表于 2022-04-09 21:10:00 回复(0)
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 返回最差情况下扔棋子的最小次数
     * @param n int整型 楼层数
     * @param k int整型 棋子数
     * @return int整型
     */
    public int solve (int n, int k) {
        // write code here
        /******************************************************************************************************/
        // 最原始的方法(最好理解)
        /*
        int[][] dp = new int[k + 1][n + 1];
        for (int j = 1; j <= n; j++) {
            dp[1][j] = j;
        }
        for (int i = 2; i <= k; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = j;
                for (int x = 1; x <= j; x++) {
                    dp[i][j] = Math.min(Math.max(dp[i - 1][x - 1], dp[i][j - x]) + 1, dp[i][j]);
                }
            }
        }
        return dp[k][n];
        */

        /******************************************************************************************************/
        // 使用二分查找
        /*
        int[][] dp = new int[k + 1][n + 1];
        for (int j = 1; j <= n; j++) {
            dp[1][j] = j;
        }
        for (int i = 2; i <= k; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = j;
                int l = 1;
                int r = j;
                int mid;
                while (l < r) {
                    mid = l + ((r - l) >> 1);
                    if (dp[i - 1][mid - 1] < dp[i][j - mid]) {
                        l = mid + 1;
                    } else {
                        r = mid;
                    }
                }
                dp[i][j] = Math.min(Math.max(dp[i - 1][l - 1], dp[i][j - l]) + 1, dp[i][j]);
            }
        }
        return dp[k][n];
        */

        /******************************************************************************************************/
        // 楼层高肯定比楼层低所需要的查找次数要多
        /*
        int[][] dp = new int[k + 1][n + 1];
        for (int j = 1; j <= n; j++) {
            dp[1][j] = j;
        }
        for (int i = 2; i <= k; i++) {
            int x = 1;
            for (int j = 1; j <= n; j++) {
                dp[i][j] = j;
                while (dp[i - 1][x - 1] < dp[i][j - x]) {
                    x++;
                }
                dp[i][j] = Math.min(Math.max(dp[i - 1][x - 1], dp[i][j - x]) + 1, dp[i][j]);
            }
        }
        return dp[k][n];
        */

        /******************************************************************************************************/
        // 使用滚动数组的方式,优化存储空间
        int[][] dp = new int[2][n + 1];
        for (int j = 1; j <= n; j++) {
            dp[1][j] = j;
        }
        int cur;
        int pre;
        for (int i = 2; i <= k; i++) {
            int x = 1;
            cur = i % 2;
            pre = i % 2 == 0 ? 1 : 0;
            for (int j = 1; j <= n; j++) {
                dp[cur][j] = j;
                while (dp[pre][x - 1] < dp[cur][j - x]) {
                    x++;
                }
                dp[cur][j] = Math.min(Math.max(dp[pre][x - 1], dp[cur][j - x]) + 1, dp[cur][j]);
            }
        }
        return dp[k % 2][n];
    }
}
发表于 2022-03-21 22:13:18 回复(0)
这是中等难度?
发表于 2022-03-02 23:11:37 回复(0)
class Solution:
    def solve(self , n: int, k: int) -> int:
        # write code here
        memo={}
        def dp(n,k):
            if k==1:return n
            if n==0:return 0
            if (n,k) in memo.keys():
                return memo[(n,k)]
            res=float('Inf')
            left=1
            right=n
            while left<=right:
                mid=(left+right)//2
                broken=dp(mid-1,k-1)
                no_broken=dp(n-mid,k)
                if broken>no_broken:
                    res=min(res,broken+1)
                    right=mid-1
                else:
                    res=min(res,no_broken+1)
                    left=mid+1
            memo[(n,k)]=res
            return res
        return dp(n,k)

超时了
发表于 2022-01-17 08:26:38 回复(0)
class Solution {
public:
    /**
dp[n][k]:n层k个棋子的最少次数
第t层测试只有两种状态 碎没碎 碎就算第t-1层 k-1个棋子
没碎:算第n-t层k个棋子
则dp[n][k]=min(dp[n][k], 1+max(dp[t-1][k-1],dp[n-t][k]))
进阶:
通过棋子凑能测试的高
dfs(k,t):k个棋子t次尝试,能测的最高楼层高度
每次测试只有碎和没碎 
dfs(k,t)=dfs(k,t-1)+dfs(k-1,t-1)
     */
    int dfs(int k, int t){
        if(t==1||k==1)return t+1;
        return dfs(k-1,t-1)+dfs(k, t-1);
    }
    int solve(int n, int k) {
        // write code here
        int t = 1;
        while(dfs(k,t)<n+1)t++;
        return t;
    }
};

发表于 2021-11-18 11:09:21 回复(0)
from functools import lru_cache
class Solution:
    def solve(self, n, k):
        @lru_cache()
        def f(i, n):
            if i == 1:return n
            if n == 1:return 1
            return f(i, n-1) + f(i-1, n-1) + 1
        res = 1
        while f(k, res) < n:
            res += 1
        return res

发表于 2021-08-13 20:29:30 回复(0)