题解 | #丢棋子问题#

思路

• 动态规划（k棋n层）：dp(k,n)表示有k个棋子n层楼需要尝试的次数，题干要求的是dp(k,n)的结果，我们现在选择在第i层扔棋子
  如果棋子碎了，则剩下k-1个棋子，此时找的楼层更新为i-1（低楼层），即应该继续尝试的次数为dp(k-1,i-1)
  如果棋子没碎，则剩下k个棋子，此时要找的楼层更新为n-i（高楼层），即应该继续尝试的次数为dp(k,n-i)
  • 这两者我们应该取一个大的值，因为是对于未知的i来说最保险的尝试次数，则应该取尝试次数现在应该为1+max(dp(k-1,i-1), dp(k,n-i))
  • 我们这么多从第i层选择扔棋子的方案跟层高n有关，所以想要得到其中最少的次数，则需求
    
• 动态规划+二分优化
  • 观察最内层进行比较的数字规律，从左到右是升序的
  • 如果是升序我们还通过遍历的方法，一定是没有利用到升序的特点的。所以升序该给我们的第一个想法就应该是二分，省成 O(logn) 的时间，这是需要锻炼的想法
  • max(dp[i][j-m],dp[i-1][m-1])我们选取的数字上一行选取索引为 m-1 的数字的时候，下一行选取的就是 j-m（因为上下两行本来是升序的，但是我们在选点的时候是上一行升序选取，下一行倒序为降序选取的，这里要把索引值对应起来）
  • 这里的二分的思路其实应该看(dp[i][j-m],dp[i-1][m-1])两者之间的差值，二者作差的差值是单调的！！！
  • 然后我就直接标记 l=0,r=j-1 作为边界，然后取mid值，其实我这里比大小的思想就是看差值的~利用这个单调性进行二分
  • 根据三张图来看，有一种情况是不重合的情况，这里单独做了一个abs(l-r)==1的条件判断，也返回一个值在这里！
• 改变思路，从尝试k个棋子n层楼找方案，改变为k个棋子尝试t次可以满足最高的层高i，只有满足到层高n才算结束，t则是最终结果。

方法一：动态规划（超时or超空间）（传统二维数组解法）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回最差情况下扔棋子的最小次数
     * @param n int整型 楼层数
     * @param k int整型 棋子数
     * @return int整型
     */
    int solve(int N, int K) {
        // write code here
        vector<vector<int>> dp(K+1,vector<int>(N+1,N));
        for(int i=0;i<=K;i++) dp[i][0]=0;        // 层高=0的时候不需要次数
        for(int i=0;i<=N;i++) dp[0][i]=0;        // 棋子=0的时候不需要次数
        for(int i=1;i<=K;i++) dp[i][1]=1;        // 层高=1的时候只需要试1次
        for(int i=1;i<=N;i++) dp[1][i]=i;        // 棋子=1的时候则需要试i次

        for(int i=2;i<=K;i++){
            for(int j=2;j<=N;j++){
                for(int m=1;m<=j;m++){
                    dp[i][j]=min(dp[i][j],max(1+dp[i][j-m],1+dp[i-1][m-1]));    // 根据转移方程列出的表示式
                }
        return dp[K][N];
    }
};

复杂度分析——最终超时超空间

• 时间复杂度：O(kN^2)，三重循环的时间代价
• 空间复杂度：O(KN)，二维数组存储每个解

方法二：动态规划+二分优化（超空间不超时）

我们在原有的基础上采用二分的思想来做最小值的选取比较查找，由于在求min的过程中，dp(k-1,i-1)随着i的增大而增大，dp(k,n-i)随着i的增大而减小，因此在求这两者最大的最小时，他们两个值只要谁高谁就不能取，但是还是要取这两个高的部分里面最小的，我们定义为权衡值。

• 两者随i的变化是有序的变化，因此考虑用二分的方法来求
• 当i-1 = mid时候，n-i = n-1-mid，所以两个值变成了dp(k-1,mid) dp(k, n-i-mid)在比大小
  • 如果dp(k-1,mid)小，由于它单增，则权衡值在mid右侧，则l = mid再循环查找
  • 如果dp(k-1,mid)大，由于它单增，则权衡值在mid左边，则r = mid再循环查找
    直到abs(l-r) == 1时候，当前的值就达到了权衡值的要求

class Solution {
public:
    int solve(int N, int K) {
        vector<vector<int>> dp(K+1,vector<int>(N+1,N));
        for(int i=0;i<=K;i++) dp[i][0]=0;        // 层高=0的时候不需要次数
        for(int i=0;i<=N;i++) dp[0][i]=0;        // 棋子=0的时候不需要次数
        for(int i=1;i<=K;i++) dp[i][1]=1;        // 层高=1的时候只需要试1次
        for(int i=1;i<=N;i++) dp[1][i]=i;        // 棋子=1的时候则需要试i次

        for(int i=2;i<=K;i++){
            for(int j=2;j<=N;j++){
                // for(int m=1;m<=j;m++){
                //     dp[i][j]=min(dp[i][j],max(1+dp[i][j-m],1+dp[i-1][m-1]));
                // }

                // 看上面第三重循环的遍历范围是  dp[i-1][0] ~ dp[i-1][j-1] 因此对应上一行选取的dp数组用的是x=0 ~ j-1
                //               所以对应关系为  dp[i][j-1] ~ dp[i][0]
                // x = 0 to j-1 找所有对儿 (每对组合中最大值)的最小值：上一行索引=x,下一行索引=j-1-x
                int l=0;
                int r=j-1;
                while(l<r){                //二分查找
                    int mid=(l+r)/2;
                    int idx=j-1-mid;
                    if(abs(l-r)==1) {dp[i][j]=1+max(dp[i][l],dp[i-1][r]);break;}    // 查找结束
                    if(dp[i-1][mid]==dp[i][idx]) {dp[i][j]=dp[i][idx]+1;break;}     // 直接找到最终结果
                    if(dp[i-1][mid]>dp[i][idx]) {r=mid;continue;}  //如果dp(k-1,mid)大，由于它单增，则权衡值在mid左侧，则r = mid再循环查找 
                    if(dp[i-1][mid]<dp[i][idx]) {l=mid;continue;}  //如果dp(k-1,mid)小，由于它单增，则权衡值在mid右侧，则l = mid再循环查找
                }

            }
        }
        return dp[K][N];
    }
};

复杂度分析

• 时间复杂度：O(knlogn)，我们将前一种方案寻找min的方法的O(n)量级缩小到了O(logN)
• 空间复杂度：O(kn)，我们需要kn的空间状态存储每个解

方法三：改变思路为【棋子方法凑层高】（通过）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回最差情况下扔棋子的最小次数
     * @param n int整型 楼层数
     * @param k int整型 棋子数
     * @return int整型
     */
    int calF(int k, int t) {
        if(t == 1 || k == 1) return t + 1;            // 如果只有一次尝试机会或者棋子只有一个，则只能确定尝试机会+1数量的楼层哪一层棋子会碎
        return calF(k - 1, t - 1) + calF(k, t - 1);   // 非上述情况则递归（棋子-1，则机会-1）和（棋子没碎，机会-1）
    }

    int solve(int n, int k) {
        // write code here
        int t = 1;
        while(calF(k, t) < n + 1) t++;                // 凑够n层的时候输出尝试的次数
        return t;
    }
};

复杂度分析

• 时间复杂度：O(nt)，t就是最终的结果，其实就是尝试t的过程，一直给t赋值+1然后凑到n层为止
• 空间复杂度：O(t)，递归栈空间的大小