算法动态规划

单峰性与二分优化DP：N个鸡蛋掉落问题

字数统计: 3.4k字   |   阅读时长: 14分
, , , ,

摘要: 单峰性、二分优化 DP

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

我们知道如果一个序列是呈现出单调性的时候，经常设计基于二分的算法。对于动态规划的状态转移方程中，最优决策候选集合有时会呈一串序列，例如：

在推导状态 $dp[i][k]$ 时，$1 \leq j \leq k$ 均对应一个决策，我们要求的是 $f(j, i, k)$ 在 $1\leq j \leq k$ 范围内的极小值。

常规方法是一一枚举，时间复杂度 $O(k)$。我们需要根据决策候选集 $1 \leq j \leq k$ 以及目标函数 $f(j, i, k)$ 的情况，设计高效找到最优决策的算法，避免枚举决策候选集。

本文看一个基于经典问题：鸡蛋掉落。其决策候选集以及目标函数涉及到决策单调性以及单峰性这两种好的性质。

决策候选集与最优决策

如果 $f(j, i, k)$ 具备某些好的性质的话，就可以通过某些方法将 $[1, k]$ 中的一些肯定达不到最优的那些决策从最优决策候选集中剔除出去。

决策空间剪枝

一种方法是通过观察到 $f(j, i, k)$ 得一些性质或引理，将决策的范围缩小，在缩小后的范围中取到的最优决策，作为整个 $[1, k]$ 范围的最优策略。相当于是对 $j$ 的搜索空间的剪枝，这种剪枝的正确性经常基于一些不等式，有时可以将决策候选集的规模降为 $O(1)$，参考文章：

决策单调性

还有一种比较好的性质是决策单调性，即随着状态 $k$ 的推导，$j$ 的范围 $[1, k]$ 随着 $k$ 变大的时候，$f(j, i, k)$ 的最优决策 $opt(i, k)$ 也随着 $k$ 递增。这样在从小到大枚举 $k$ 时，$j$ 的最优决策下限就是 $opt(i, k-1)$，这样就把比 $opt(i, k - 1)$ 小的决策排除掉了。

如果目标函数 $f(j, i, k)$ 与 $k$ 无关，那么决策候选集单调增加时目标函数不变，这是决策单调性的简单情况，参考以下三篇文章：

如果目标函数 $f(j, i, k)$ 与 $k$ 有关，那么决策候选集单调增就不是很好发现了，需要一些归纳和推导。本文的题目是一个例子。

决策目标函数的单峰性

如果 $f(j, i, k)$ 在固定 $i, k$ 时，对 $j$ 呈现单峰性，那么二分地找 $j$ 的最优决策就是可以考虑的办法。虽然不像直接剪枝那样直接排除掉大量决策，但二分可以在每查找一次决策候选集就排除掉一半决策，状态转移到额时间复杂度就变成 $O(\log k)$，效果也很可观。

关于函数的单调性、凸性、单峰性等概念及其性质可以参考文章 一元函数的单调性、凸性与单峰性。求单峰函数的极值的三分算法参考 单峰性与三分查找。

887. 鸡蛋掉落

给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。

已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。

每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。

请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？

提示：

1
2
1 <= k <= 100
1 <= n <= 1e4

示例 1：
输入：k = 1, n = 2
输出：2
解释：
鸡蛋从 1 楼掉落。如果它碎了，肯定能得出 f = 0 。
否则，鸡蛋从 2 楼掉落。如果它碎了，肯定能得出 f = 1 。
如果它没碎，那么肯定能得出 f = 2 。
因此，在最坏的情况下我们需要移动 2 次以确定 f 是多少。

示例 2：
输入：k = 2, n = 6
输出：3

示例 3：
输入：k = 3, n = 14
输出：4

试验与观察

记鸡蛋有 $N$ 枚，要确认的楼层数为 $H$。

首先最坏的情况下，也就是只有一枚鸡蛋 $N=1$，我们要对未知的范围 $1$ 到 $H$ 中，就只能从第 1 层、第 2 层，依次线性地试验，在最坏情况下需要试 $H$ 次。

如果有 $N = 2$ 枚鸡蛋，那么第一枚的时候就不用从小到大依次尝试了，而可以从中间某个位置尝试，假设在 $1 \leq h \leq H$ 范围某一层 $h$ 尝试，这算是一步操作，分鸡蛋碎和不碎两种情况讨论。

如果碎了，那么鸡蛋只剩一个了，这时就变成了 $N=1$ 的情况，此时 $h$ 到 $H$ 就已知了，未知范围为 $1$ 到 $h-1$ 之间，答案是 $h-1$。

如果没碎，则鸡蛋还是两个，此时 $1$ 到 $h$ 已知了，未知范围在 $h+1$ 到 $H$ 之间。相当于找到了一个规模更小的子问题。

算法：动态规划

定义 $dp[i][l][h]$ 表示当前有 $i$ 枚鸡蛋，未知楼层在 $l$ 到 $h$ 时，确认出临界楼层所需最小操作次数。这里 $i$ 是阶段，$l, h$ 是附加信息。

这样定义的话，初始值为鸡蛋个数为 1 的情况 $dp[1][l][h] = h - l + 1$，以及 $l > h$ 时 $dp[i][l][h] = 0$，答案为 $dp[N][1][H]$。下面考虑 $i > 1$ 时的状态转移。

在 $l, h$ 中间选择 $k$ 进行尝试，这是一步操作，分鸡蛋碎和不碎两种情况讨论：

  • 如果碎了，那么鸡蛋剩 $i - 1$ 个，此时未知楼层变为 $l, k-1$，最终需要的步数为 $1 + dp[i-1][l][k-1]$。
  • 如果没碎，鸡蛋还是 $i$ 个，此时未知楼层变为 $k+1,h$，最终需要的步数为 $1 + dp[i][k+1][h]$

这一步选择 $k$，最终的操作次数取决于上面两种情况所需步数的较大值，所以状态转移方程如下：

状态共 $O(NH^{2})$ 个，状态转移需要 $O(H)$，所以总时间复杂度 $O(NH^{3})$。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def superEggDrop(self, N: int, H: int) -> int:

        @lru_cache(int(1e8))
        def solve(i: int, l: int, h: int) -> int:
            if l > h:
                return 0
            if i == 1:
                return h - l + 1

            ans = h - l + 1
            for k in range(l, h+1):
                tmp = 1 + max(solve(i - 1, l, k - 1), solve(i, k + 1, h))
                ans = min(ans, tmp)

            return ans

        return solve(N, 1, H)

优化状态表示

对于 $dp[i][l][h]$ 来说，我们要求最小步数并不关心具体的层数范围，只关心范围内有多少层。所以可以把 $l, h$ 这两个附加信息合并成一个 $k$，$dp[i][k]$ 表示当前有 $i$ 个鸡蛋，未知层的个数为 $k$ 时的最小操作次数。

这样定义的话，答案为 $dp[N][H]$，初始值为 $dp[1][k] = k$，$dp[i][0] = 0$。状态转移方程如下：

状态共 $O(NH)$ 个，状态转移需要 $O(H)$，所以总时间复杂度为 $O(NH^{2})$。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def superEggDrop(self, N: int, H: int) -> int:

        @lru_cache(int(1e8))
        def solve(i: int, k: int) -> int:
            if k == 0:
                return 0
            if i == 1:
                return k

            ans = k
            for j in range(1, k+1):
                tmp = 1 + max(solve(i - 1, j - 1), solve(i, k - j))
                ans = min(ans, tmp)

            return ans

        return solve(N, H)

优化1：二分优化DP

回顾状态转移方程，可以写成以下形式：

其中 $f(j, i, k) = 1 + \max(dp[i-1][j-1], dp[i][k-j])$。

通过分析可以知道 $dp[i - 1][j - 1]$ 关于 $j$ 是单调递增函数，$dp[i][k-j]$ 关于 $j$ 是单调递减函数。

于是 $\max(dp[i-1][j-1], dp[i][k-j])$ 关于 $j$ 的单峰函数。可以通过三分的方法求极值，这里是离散的情况，也可以用二分，具体过程如下：

对于给定的 $i, k$，在 $j$ 的范围 $[1, k]$ 内二分，对于当前二分的 $mid$，记 $T_{1} = dp[i - 1][mid - 1], T_{2} = dp[i][k - mid]$：

  • 如果 $T_{1} < T_{2}$，说明 $mid$ 取小了，置 $left = mid + 1$；
  • 如果 $T_{1} > T_{2}$，说明 $mid$ 取大了，置 $right = mid - 1$；
  • 如果 $T_{1} = T_{2}$，说明已找到最优决策。

状态共 $O(NH)$ 个，状态转移需要 $O(\log H)$，所以总时间复杂度为 $O(NH\log H)$。

代码 (C++)

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
27
28
29
30
31
class Solution {
public:
    int superEggDrop(int N, int H) {
        vector<vector<int> > dp(N + 1, vector<int>(H + 1, INT_MAX));
        for(int i = 0; i <= N; ++i)
            dp[i][0] = 0;
        for(int k = 1; k <= H; ++k)
            dp[1][k] = k;

        for(int i = 2; i <= N; ++i)
            for(int k = 1; k <= H; ++k)
            {
                // 二分地从 [1..k] 找 j
                int left = 1, right = k;
                while(left <= right)
                {
                    int mid = left + (right - left) / 2;
                    int T1 = dp[i - 1][mid - 1];
                    int T2 = dp[i][k - mid];
                    dp[i][k] = min(dp[i][k], max(T1, T2) + 1);
                    if(T1 > T2) // mid 大了
                        right = mid - 1;
                    else if(T1 < T2) // mid 小了
                        left = mid + 1;
                    else // 已经找到最优决策
                        break;
                }
            }
        return dp[N][H];
    }
};

代码 (Python)

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
27
28
29
30
class Solution:
    def superEggDrop(self, N: int, H: int) -> int:

        @lru_cache(int(1e8))
        def solve(i: int, k: int) -> int:
            if k == 0:
                return 0
            if i == 1:
                return k

            ans = k
            # 二分地从 [1, k] 中找 j
            left = 1
            right = k
            while left <= right:
                mid = (left + right) // 2
                T1 = solve(i - 1, mid - 1)
                T2 = solve(i, k - mid)
                ans = min(ans, max(T1, T2) + 1)
                if T1 > T2:
                    right = mid - 1
                elif T1 < T2:
                    left = mid + 1
                else:
                    # 找到最优决策
                    break

            return ans

        return solve(N, H)

优化2：决策单调性

回顾状态转移方程：

$dp[i-1][j-1]$ 是 $j$ 的单调递增函数，与 $k$ 无关；$dp[i][k-j]$ 是单调递减函数，如果视其为一条曲线，那么当 $k$ 变化时，$dp[i][k-j]$ 构成曲线族，并且随着 $k$ 增加，曲线向右上平移，如下图：

记 $p = opt(i, k)$ 表示 $dp[i][k]$ 的最优决策点，可以看出，随着 $k$ 增加，最优决策点的位置 $opt(i, k)$ 也增加，也就是构成决策单调性。

由上述决策单调性，因此在推导 $dp[i][k]$ 时，$j$ 在小于 $opt(i, k-1)$ 的值上不可能取到最优。但是 $opt(i, k-1), opt(i, k-1)+1, \cdots, k$ 范围内在哪取到极值的问题还是要解决。

这里有一个基于问题的额外性质，本质也是前面二分算法用到的单峰性。记 $T_{1}(j) = dp[i - 1][j - 1], T_{2}(j) = dp[i][k - j]$，则最优决策 $opt(i, k)$ 为：

  • 满足 $\max(T_{1}(j), T_{2}(j)) \leq \max(T_{1}(j+1), T_{2}(j+1))$ 的最小的 $j$；
  • 或者是 $T_{1}(j) \geq T_{2}(j)$ 的最小的 $j$。

于是在推导 $k$ 时，可以用一个变量 $j$ 记录最优决策，并用上述两个性质之一推进 $j$。事实上推进的部分就是上图中的 $opt(i, k-1)$ 到 $opt(i, k)$。

共 $NH$ 个状态，状态转移的时间复杂度摊销 $O(1)$，总时间复杂度 $O(NH)$。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int superEggDrop(int N, int H) {
        vector<vector<int> > dp(N + 1, vector<int>(H + 1));
        for(int i = 0; i <= N; ++i)
            dp[i][0] = 0;
        for(int k = 1; k <= H; ++k)
            dp[1][k] = k;

        for(int i = 2; i <= N; ++i)
        {
            int j = 1; // 最优决策随着 k 单调增加
            for(int k = 1; k <= H; ++k)
            {
                // while (j < k && max(dp[i - 1][j - 1], dp[i][k - j]) > max(dp[i - 1][j], dp[i][k - j - 1]))
                while (j <= k && dp[i - 1][j - 1] < dp[i][k - j])
                    j++;

                dp[i][k] = 1 + max(dp[i - 1][j - 1], dp[i][k - j]);
            }
        }
        return dp[N][H];
    }
};

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def superEggDrop(self, N: int, H: int) -> int:
        dp = [[0 for _ in range(H + 1)] for _ in range(N + 1)]

        for k in range(1, H + 1):
            dp[1][k] = k

        for i in range(2, N + 1):
            j = 1 # 最优决策随着 k 增加而增加
            for k in range(1, H + 1):
                while j <= k and dp[i - 1][j - 1] < dp[i][k - j]:
                    j += 1
                dp[i][k] = 1 + max(dp[i - 1][j - 1], dp[i][k - j])

        return dp[N][H]
Share