丢棋子问题（动态规划）

题意

n+1层楼,k个棋子,每次扔一个,如果坏了不能重复使用,没有坏可以重复使用,找到最高德不会摔坏层数

问最坏情况需要几次

思路分析

1个棋子的情况

只有一个棋子,摔坏了就没得猜了,只能从低到高反复用

f(i,1) = i;

2个棋子的情况

假设选取从j层丢第一个棋子

坏了, 剩下一个棋子,代价为1+(j-1) = j
没有坏,问题变为2个棋子高度为i-j的情况,再加上刚刚扔的一次

f(i,2) = min(1 + max(j-1,f(i-j,2)))

显然f(i,2)是非严格单调递增的(因为比每次+1好),j-1也是严格单调递增的,

所以随着j取值增大,min中的值一侧增大,一侧减小,有交错点

通过枚举,观察前几个值

f(1,2) = 1;
f(2,2) = 2;
f(3,2) = 2;
f(4,2) = 3;
f(5,2) = 3;
f(6,2) = 3;
f(7,2) = 4;
f(8,2) = 4;
f(9,2) = 4;
f(10,2) = 4;
f(11,2) = 5;

可以看出,规律是1个1,2个2,3个3,4个4...

f(i,2) = x; // => x(x-1)/2 < i <= x(x+1)/2

虽然啊对后续推导这个式子用处不大,但也展示了上面的非严格单调递增的性质

更一般情况

i层, k (>= 2)个棋子,从j层抛

坏了, 剩下代价为 f(j-1,k-1)
没有坏,剩下代价为f(i-j,k)

转化成递推关系

dp[i][j] = min(1 + max(dp[m-1][j-1],dp[i-m][j])); ( 1<=m<=i )

也就是

for(int i = 1;i <= n;i++){
    for(int j = 1;j < k;j++){
        for(int m = 1; m < i; m++){
            dp[i][j] = min(dp[i][j], 1 + max(dp[m-1][j-1],dp[i-m][j]));
        }
    }
}

大约是 $O (n^{2} k)$ 的时间复杂度,不幸的是,题目的n,k都很大,显然会超时

然而我们上面除了得到关系式以外还有一个收获

对于dp[i][j],如果指定了j > 1,那么必然对于i单调递增时,dp[i][j]非严格单调递增,且最大增量为1,最小增量为0,

换句话说如果dp[i][j] = v, 令maxi(j,v)表示 v 能对应的最大的下标i

有maxi(j,v) = 1 + maxi(j,v-1) + max(j-1,v-1)

而,题目变成找到v使得maxi(k,v-1)< n <=maxi(k,v),

递推实现

把上述内容转换成代码

for(int j = 1;j<=k;j++){
    for(int v = 1; dp[j][v-1] < n ;v++){
        dp[j][v] = 1 + dp[j-1][v-1] + dp[j][v-1];
    }
}

最后把dp[k][v]中最大的v输出即是要求的答案

空间压缩

注意到每个值只依赖于当前层和上一层的值,所以只用记录当前和上一层的内容.

所以只留两个一维数组,分别记录当前层和上一层的值

for(int j = 1;j<=k;j++){
    for(int v = 1; dp[v-1] < n ;v++){
        dp[v] = 1 + lastdp[v-1] + dp[v-1];
    }
}

边界处理

对于第一层,全部的值等于其下标

for(int i = 1;i<=n;i++){
	dp[i] = i;
}

每层的第一个值全部为1

for(...){
	dp[1] = 1;
}

样例数据示例

以题目样例数据2为例,所建立的dp表如图

alt

题解

所以整合上面的内容

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回最差情况下扔棋子的最小次数
     * @param n int整型 楼层数
     * @param k int整型 棋子数
     * @return int整型
     */
    int solve(int n, int k) {
        // dp[j][v] = 1 + dp[j][v-1] + dp[j-1][v-1];
        // find v: dp[k][v-1] < n <= dp[k][v]
        // 不记录 0, 坐标减去1
        vector<int> dp = vector<int>(n,0);
        for(int i = 0;i < n;i++) dp[i] = i+1; // 第一层 j == 1
        for(int j = 2;j<=k;j++){
            vector<int> dpnext = vector<int>(1,1); // 每层第一个数
            for(int v = 2;;v++){
                if(dpnext.back() >= n)break; // 超过要求的值
                dpnext.emplace_back(1+dpnext[v-2]+dp[v-2]); // 递推关系
            }
            dp = dpnext; // 只保留当前和上一层的结果
        }
        return dp.size();
    }
};

复杂度分析

空间复杂度: 存储状态数组最大为层数,所以空间复杂度为 $O (n)$

时间复杂度: 一共外层循环k次,内层最多n次,最少输出结果的次数, 而内层的次数呈log级别下降,所以时间复杂度为 $O (m a x (n, k m))$

题解 | #丢棋子问题#