🔖 quiz动态规划

问题描述

有 K 个鸡蛋和 N 层楼，测试最多试验几次可以测出让鸡蛋摔碎的最低楼层。假定鸡蛋无磨损，即如果在第 x 层楼扔下没碎，那么在第 x 层楼重复扔无限次都不会碎。没碎的鸡蛋可以重复使用（用于测试），已碎的鸡蛋无法继续使用。

算法一

将 N 层楼看作长度为 N 的区间，记 dp(k,n) 表示至多使用 k 个鸡蛋测出区间长度为 n 的楼层里任意楼层是否能摔碎鸡蛋的最少试验次数，则状态转移方程为：

dp(k,n)=min{max{dp(k−1,x−1),dp(k,n−x)}|1⩽x⩽n}+1

上式的含义是，枚举区间长度为 n 层楼中的第 x 层楼，并从此层楼扔下一枚鸡蛋：

  • 若鸡蛋碎了，则还有 k−1 个鸡蛋可以使用，并只需要需要在区间长度为 x−1 的楼层里找到答案

  • 若鸡蛋没碎，则还有 k 个鸡蛋可以使用，并只需要在区间长度为 n−x 的楼层里找到答案

不难发现，如果直接暴力枚举，复杂度将高达 O(K⋅N2)。

注意到 dp(k) 是一个非严格单调递增的向量（即 dp(k,x)⩽dp(k,x+1)，因此可以通过二分 dp(k,n) 的答案，然后找到 dp(k−1,x−1),1⩽x⩽n 中小于此答案的最大 x，然后检查 dp(k,n−x) 是否也同时小于此答案即可完整验证。此时，时间复杂度为 O(K⋅N⋅log2⁡N)

algorithm1.ts 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const MAX_K = 100 + 2
const MAX_N = 10000 + 2
const dp: number[][] = new Array(MAX_K)


function preprocess(): void {
  for (let k = 0; k < MAX_K; ++k) {
    dp[k] = new Array(MAX_N)
    dp[k][0] = 0
  }


  for (let n = 1; n < MAX_N; ++n) {
    dp[1][n] = n
  }


  for (let k = 2; k < MAX_K; ++k) {
    const f: number[] = dp[k - 1]
    const h: number[] = dp[k]
    for (let n = 1; n < MAX_N; ++n) {
      const answer = lowerBound(f[1], f[n], candidateAnswer => {
        const x = lowerBound(1, n, y => f[y] <= candidateAnswer)
        return x <= 1 || h[n - x] > candidateAnswer
      })
      h[n] = Math.min(f[n], answer + 1)
    }
  }
}

算法二

记 dp(k,m) 表示使用 k 个鸡蛋在 m 步内最多能测出的最高楼层。考虑第一次扔鸡蛋应该在哪一层扔，不妨假设最优决策是先在第 x 层扔鸡蛋：

  • 如果鸡蛋摔碎了，则必须要使用 k−1 个鸡蛋在 m−1 次里测出前 x−1 层里能使鸡蛋摔碎的最小楼层，则取 x=dp(k−1,m−1)+1 是最优的（否则，无法在条件限制内完成测试）。

  • 如果鸡蛋没摔碎，则相当于把第 x+1 层看作第一层继续测试，因此最多还能测出 dp(k,m−1) 层楼。

因此，状态转移方程为：

dp(k,m)=x+dp(k,m−1)=dp(k−1,m−1)+dp(k,m−1)+1

Related

© 2017-2025 光和尘有花满渚、有酒盈瓯

Comments