算法疑难杂症

通过不等式优化的算法问题

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

摘要: 不等式在算法优化中的应用

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

各位好，不等式经常在解决优化或最值问题时有所应用，例如均值不等式是我们高中时接触过的重要不等式，经常用于解决一些比较简单的最值问题，将函数变形去凑成均值不等式的形式，得出最值。

不等式也是算法优化时的有力手段，比如很多贪心算法的正确性都基于一些不等式。如果没有这种不等式的观察，就只能接受非贪心的算法，那时间复杂度就不优秀了。本文我们看一个例子。

题目

最初记事本上只有一个字符 ‘A’ 。你每次可以对这个记事本进行两种操作：

  • Copy All（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。
  • Paste（粘贴）：粘贴 上一次 复制的字符。

给你一个数字 n ，你需要使用最少的操作次数，在记事本上输出 恰好 n 个 ‘A’ 。返回能够打印出 n 个 ‘A’ 的最少操作次数。

示例 1：
输入：3
输出：3
解释：
最初, 只有一个字符 ‘A’。
第 1 步, 使用 Copy All 操作。
第 2 步, 使用 Paste 操作来获得 ‘AA’。
第 3 步, 使用 Paste 操作来获得 ‘AAA’。

示例 2：
输入：n = 1
输出：0

提示：

1
1 <= n <= 1000

题解

算法1：动态规划

定义 $dp[i]$ 表示当前屏幕有 $i$ 个 A，到达屏幕有 $n$ 个 A，所需经过的最少操作次数。这里操作次数为阶段，$i$ 是附加信息。但除了这一个附加信息还找不到最优子结构。

由于增加 A 的个数的唯一方式就是粘贴，这里面唯一变量是粘贴多少个 A。因此需要增加一个信息 $j$，表示当前剪切板中有 $j$ 个 A。

刚开始时，屏幕有 1 个 A，剪切板中有 0 个 A，因此答案为 $dp[1][0]$，第两步只能执行复制再粘贴的操作，这样剪切板中变为 1 个 A，屏幕上是 2 个 A，于是 $dp[1][0] = 2 + dp[2][1]$。

下面考虑初始化问题。当 $i = n$ 时，已经达到了想要的 A 的个数，因此 $dp[n][\cdots] = 0$。

此外还会有无法转移到 $dp[n][\cdots]$ 的情况，也就是 $i$ 无法整除 $n$，同时 $j$ 也无法整除 $n - i$ 的情况。这种情况记 $dp[i][j] = INF$。

下面考虑状态转移方程：

对于 $dp[i][i]$，只能执行粘贴，转移到 $1 + dp[2i][i]$；

对于 $dp[i][j], j < i$，则可以执行粘贴，转移到 $1 + dp[i + j][j]$，也可以执行复制，转移到 $1 + dp[i][i]$，也就相当于转移到 $2 + dp[2i][i]$。在这两种决策中选择最优的即可。

代码 (Python)

共 $O(N^{2})$ 个状态，时间复杂度为 $O(N^{2})$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
INF = int(1e9)

class Solution:
    def minSteps(self, n: int) -> int:
        @lru_cache(int(1e7))
        def solve(i: int, j: int) -> int:
            if i == n:
                return 0
            if n % i != 0 and (n - i) % j != 0:
                return INF
            ans = INF
            if solve(i + j, j) != INF:
                ans = min(ans, 1 + solve(i + j, j))
            if j < i and solve(i * 2, i) != INF:
                ans = min(ans, 2 + solve(i * 2, i))
            return ans

        if n == 1:
            return 0
        return 2 + solve(2, 1)

算法2：数论、不等式

将 1 次复制和 x 次粘贴合到一起，记为一轮复制粘贴。

从初始的屏幕上只有 1 个 A，剪切板里没有 A 开始。经过若干轮复制粘贴，使得屏幕上有 n 个 A。

一轮复制粘贴使得原来的长度 $l$ 变为 $l(x + 1)$。

假如一共进行了 $k$ 轮，第 i 轮进行 1 次复制和 $x_{i}$ 次粘贴。这样 $k$ 轮复制粘贴后的总长度为：

目标是屏幕上有 $n$ 个 A，因此就要：

记 $y_{i} = 1 + x_{i}$，这样问题就变成了如何将 $n$ 分解为若干个数的乘积 $n = \prod\limits_{i = 1}\limits^{k}y_{i}$，使得总操作次数 $\sum\limits_{i=1}\limits^{k}y_{i}$ 最小。

引理(不等式)

当 $a \geq 2, b \geq 2$ 时，$ab \geq a + b$。

证明

做商：

由于 $a, b \geq 2$，有 $\frac{1}{a} \leq \frac{1}{2}$，$\frac{1}{b} \leq \frac{1}{2}$。因此 $\frac{1}{a} + \frac{1}{b} \leq 1$

于是 $\frac{a + b}{ab} \leq 1$，即 $a + b \leq ab$。

$\Box$

假设目前将 $n$ 分解为了 $n = ab$，此时的总操作次数为 $a + b$。$b$ 可以进一步分解为 $b = cd$，若执行这步分解，则总操作次数变为 $a + c + d$。由上述引理，由于 $c, d \geq 2$，有 $b = cd \geq c + d$。因此 $a + b \geq a + c + d$，也就是总操作次数可能不变也可能变小。

这样我们就可以尽可能将 $n$ 多分解，直至不能分解，最终会分解为若干个质数的乘积 $n = p_{1}^{n_{1}}\cdots p_{k}^{n_{k}}$。对应的总操作次数为 $\sum\limits_{i=1}\limits^{k}n_{i}p_{i}$

因此最终算法就是，对 $p = 2,3,\cdots,n$ 的每个数进行试除，若质数 $p$ 能整除 $n$，且 $n$ 的展开式中 $p$ 的次数为 $k$，则将答案 $res$ 加 $kp$，将 $n$ 更新为 $\frac{n}{p^{k}}$，然后进行下一个质数 $p$，直至 $n$ 变成 $1$。

时间复杂度为 $O(\sqrt{N})$。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minSteps(int n) {
        int res = 0;
        int p = 2;
        while(n > 1)
        {
            while(n % p == 0)
            {
                res += p;
                n /= p;
            }
            p++;
        }
        return res;
    }
};
Share