题意整理

  • 给定整数n作为楼层数，再给定整数k作为棋子数。
  • 如果想找到棋子不会摔碎的最高层数，考虑最差的情况下，至少需要扔多少次棋子。

方法一（暴力递归）

1.解题思路

  • 递归终止条件：0层时，不需要确定，返回0次；一枚棋子时，需要一个一个地试，返回n。

  • 递归如何推进：假设当前为第i层，要么棋子碎了，需要扔dfs(i-1,k-1)+1次,要么棋子没碎，需要扔dfs(n-i,k)+1次，取较大者。并且统计所有层的情况，取最小的次数。

  • 每一层返回什么：返回当前层的最小次数。

当层数n较大时，这种方法会报栈深度溢出的错误。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回最差情况下扔棋子的最小次数
     * @param n int整型 楼层数
     * @param k int整型 棋子数
     * @return int整型
     */
    public int solve (int n, int k) {
        //递归
        return dfs(n,k);
    }
    
    private int dfs(int n,int k){
        //0层时，不需要确定，返回0次
        if(n==0) return 0;
        //一枚棋子时，一个一个试，返回n
        if(k==1) return n;
        int min=Integer.MAX_VALUE;
        for(int i=1;i<=n;i++){
            /*第i层时，如果棋子碎了则需要扔dfs(i-1,k-1)+1次,如果没碎，则
            需要扔dfs(n-i,k)+1次，取较大者，记录所有可能的最小次数*/
            min=Math.min(min,Math.max(dfs(i-1,k-1),dfs(n-i,k))+1);
        }
        return min;
    }
}

3.复杂度分析

  • 时间复杂度：最坏情况下，每次大问题的规模减1，递归里还嵌套着一个循环，所以时间复杂度为O(n!)O(n!)。
  • 空间复杂度：最坏情况下，递归的层数为n，所以空间复杂度是O(n)O(n)。

方法二（动态规划）

1.解题思路

首先求出层数n需要的二分次数cnt，如果k大于等于cnt，则可以通过二分的策略确定最高层数，直接返回cnt。如果k小于cnt，可以先求出i枚棋子能确定的最高层数，一旦这个数大于等于n，直接返回对应扔棋子的次数。

  • 状态定义：dp[i]dp[i]表示棋子数为i时，可确定的最高层数。
  • 状态初始化：只有一枚棋子时，仍多少次确定多少层，即dp[1]=timedp[1]=time。
  • 状态转移：扔第i枚棋子时，如果棋子碎了，向下可以确定dp[i−1]dp[i-1]层，如果没碎，向上可以确定dp[i]dp[i]层，再加上当前层，所以dp[i]+=dp[i−1]+1dp[i]+=dp[i-1]+1。

图解展示： alt

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回最差情况下扔棋子的最小次数
     * @param n int整型 楼层数
     * @param k int整型 棋子数
     * @return int整型
     */
    public int solve (int n, int k) {
        //只有1个棋子时，需要一个一个试，返回n
        if(k==1) return n;
        //棋子数足够多时，每仍一枚棋子可排除一半的层数，理想情况下正好是对应二分的次数
        int cnt=(int)(Math.log(n)/Math.log(2))+1;
        if(k>=cnt) return cnt;
        
        //dp[i]表示棋子数为i时，可确定的最高层数
        int[] dp=new int[k+1];
        //记录仍棋子的最小次数
        int time=1;
        while(true){
            for(int i=k;i>=1;i--){
                /*如果棋子碎了，向下可以确定dp[i-1]层，如果没碎，
                向上可以确定dp[i]层，再加上当前层，所以dp[i]+=dp[i-1]+1*/
                dp[i]+=dp[i-1]+1;
                if(dp[i]>=n){
                    return time;
                }
            }
            //只有一枚棋子时，仍多少次确定多少层
            dp[1]=time++;
        }
    }
   
}

3.复杂度分析

  • 时间复杂度：外层循环最多执行log2nlog_2n次，内层循环执行k次，所以时间复杂度为O(klog2n)O(klog_2n)。
  • 空间复杂度：需要额外大小为k+1的dp数组，所以空间复杂度是O(k)O(k)。