首页 > 试题广场 >

丢棋子问题

[编程题]丢棋子问题
  • 热度指数：19354 时间限制：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
牛客189410298号头像 牛客189410298号

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 回复(1)
提交观点

问题信息

动态规划
难度：
1条回答 5172浏览

热门推荐

通过挑战的用户

查看代码

相关试题

丢棋子问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号