算法动态规划

剪枝优化DP：基于数学性质排除大量无效决策

字数统计: 1.6k字   |   阅读时长: 6分
, , ,

摘要: 剪枝策略减少最优决策候选集中的无效决策

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

在基于动态规划解决最优性问题时，状态转移方程中，一个状态对应着很多决策。常规的方式是把这些决策都遍历一遍，取目标可以达到最值的那个决策。

但有时状态转移方程满足一些性质，使得我们可以将一些肯定不会是最优的决策排除在外，这样最优决策候选集的规模就会较小，相当于对搜索空间进行了剪枝。从而达到优化的效果。剪枝后留下的搜索空间中有最优决策这件事需要证明。

本文我们看 1 个例子。

651. 4键键盘

假设你有一个特殊的键盘包含下面的按键：

  • A：在屏幕上打印一个 ‘A’。
  • Ctrl-A：选中整个屏幕。
  • Ctrl-C：复制选中区域到缓冲区。
  • Ctrl-V：将缓冲区内容输出到上次输入的结束位置，并显示在屏幕上。

现在，你可以 最多 按键 n 次（使用上述四种按键），返回屏幕上最多可以显示 ‘A’ 的个数 。

示例 1:
输入: n = 3
输出: 3
解释:
我们最多可以在屏幕上显示三个’A’通过如下顺序按键：
A, A, A

示例 2:
输入: n = 7
输出: 9
解释:
我们最多可以在屏幕上显示九个’A’通过如下顺序按键：
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V

提示:

1
1 <= n <= 50

算法: 动态规划

定义 $dp[i]$ 表示按 $i$ 次键可得最多的 A 的个数。其中 $i$ 表示阶段。

在第 $i$ 阶段，最多有 $dp[i]$ 个 A，这些 A 有两个来源：

  • 法1，加法：按下 KEY1，增加一个 A；
  • 法2，乘法：按下 KEY4，将已有的内容粘贴一份。

因为在按下 KEY4 之前需要先按下 KEY2 + KEY3，因此法2 需要在剩余步数大于等于 3 时才可以用。

根据 KEY2 + KEY3 按下的不同时机，法2 会有多种决策，例如在第 $i-3$ 阶段的最大长度为 $dp[i-3]$，然后将 $dp[i-3]$ 经过选中、复制、粘贴 3 步，长度变为原来 2 倍，即 $2dp[i-3]$，也可以是在第 $i-4$ 阶段，将 $dp[i-4]$ 经过选中、复制，再粘贴两次，长度变为原来 3 倍，即 $3dp[i-4]$。

一般地，可以在第 $i - j$ 阶段，将 $dp[i-j]$ 经过选中，复制，再粘贴 $j-2$ 次，长度变为 $j - 1$ 倍。这里 $3 \leq j \leq i - 2$，综上，状态转移方程为：

共 $O(N)$ 个状态，每次转移需要 $O(N)$，总时间复杂度 $O(N^{2})$。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxA(int N) {
        if(N == 0) 
            return 0;
        vector<int> dp(max(4, N + 1));
        dp[1] = 1;
        for(int i = 2; i <= N; ++i)
        {
            dp[i] = dp[i - 1] + 1;
            for(int j = 3; j <= i - 2; ++j)
                dp[i] = max(dp[i], dp[i - j] * (j - 1));
        }
        return dp[N];
    }
};

剪枝优化DP：基于数学性质

将 $dp[i]$ 的状态转移方程中 $\max\limits_{3 \leq j \leq i - 2}dp[i - j] \times (j - 1)$ 这部分展开，如下：

引理

在最优决策中，连续粘贴的次数不会超过 5。

证明

假设 $dp[i]$ 已经推导完成，也就是 $i$ 次操作可以取得的 A 的最多个数为 $dp[i]$。下面考虑从 $dp[i]$ 开始全选、复制，若干次粘贴，$dp[i]$ 可以作为后续哪些状态的决策候选集。

假设经过全选、复制，再经过 $k-1$ 次粘贴，可以在按 $i + k + 1$ 次键时，将 $dp[i]$ 个 A 变为 $k \times dp[i]$ 个 A。下面分 $k$ 为奇数和偶数分别讨论。

(1) $k = 2n$ 为偶数，则相当于经过 $2n + 1$ 步操作，在第 $i + 2n + 1$ 次按键时，将 $dp[i]$ 个 A 变为 $2n \times dp[i]$ 个 A。

但是另一方面，还可以首先经过 $n + 1$ 步操作，将 $dp[i]$ 个 A 变为 $n \times dp[i]$ 个 A，然后再经过 3 步，也就是在第 $i + n + 4$ 次按键时，将 $dp[i]$ 个 A 变为 $2n \times dp[i]$ 个 A。

当 $n \geq 3$ 时，$2n + 1 \geq n + 4$，此时 $2n \times dp[i]$ 不会是 $dp[i + 2n + 1]$ 的最优决策。因为 $dp[i + n + 4]$ 就已经达到 $2n \times dp[i]$ 个 A 了。

(2) $k = 2n + 1$ 为奇数，则相当于经过 $2n + 2$ 步操作，在第 $i + 2n + 2$ 次按键时，将 $dp[i]$ 个 A 变为 $(2n + 1)dp[i]$ 个 A。

但是另一方面，还可以首先经过 $n + 2$ 步操作，将 $dp[i]$ 个 A 变为 $(n + 1)dp[i]$ 个 A，然后再经过 3 步，也就是在第 $i + n + 5$ 次按键时，将 $dp[i]$ 个 A 变为 $(2n + 2) dp[i]$ 个 A。

当 $n \geq 3$ 时，$2n + 2 \geq n + 5$，此时 $(2n + 1)dp[i]$ 不会是 $dp[i + 2n + 2]$ 的最优决策，因为 $dp[i + n + 5]$ 就已经达到 $(2n + 2)dp[i]$ 个 A 了。

综上，当 $k < 6$ 时，经过 $k+1$ 步操作，在第 $i + k + 1$ 次按键时将 $dp[i]$ 个 A 变为 $k \times dp[i]$ 个 A （即把 $dp[i]$ 个 A 连续粘贴 $k$ 次）才有可能是最优决策。

因此，在最优决策中，连续粘贴次数不会超过 5。

$\Box$

有了上述引理，状态转移方程就可以变为：

在推导 $dp[i]$ 时，加法的决策依然要考虑，乘法的决策仅考虑 $k \leq 5$ 的部分。通过剪枝策略，$k > 5$ 的这部分决策被优化掉了。总时间复杂度变为 $O(N)$。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxA(int N) {
        if(N == 0) 
            return 0;
        vector<int> dp(max(4, N + 1));
        dp[1] = 1;
        for(int i = 2; i <= N; ++i)
        {
            dp[i] = dp[i - 1] + 1;
            for(int k = 2; k <= min(i - 3, 5); ++k)
                dp[i] = max(dp[i], dp[i - k - 1] * k);
        }
        return dp[N];
    }
};
Share