一座大楼有 n+1 层，地面算作第0层，最高的一层为第 n 层。已知棋子从第0层掉落肯定不会摔碎，从第 i 层掉落可能会摔碎，也可能不会摔碎。
给定整数 n 作为楼层数，再给定整数 k 作为棋子数，返回如果想找到棋子不会摔碎的最高层数，即使在最差的情况下扔的最小次数。一次只能扔一个棋子。
数据范围： 
要求：空间复杂度 )
，时间复杂度 )
(m是最终返回的结果)
[编程题]丢棋子问题
- 热度指数：18961 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
示例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便是结果
备注:
四边形不等式都超时，真的离谱离到姥姥家。
非得用那个最神奇的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);
}
}
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)
解题思路：由初始的二维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)
问题信息
难度：
5条回答
498收藏
4658浏览
通过挑战的用户
查看代码-
2022-11-17 15:41:09
-
2022-09-15 10:19:25 -
2022-09-14 18:19:12 -
2022-09-14 12:30:13 -
2022-09-14 00:51:06
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
