Processing math: 29%

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

  |  

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

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的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][]=0

此外还会有无法转移到 dp[n][] 的情况,也就是 i 无法整除 n,同时 j 也无法整除 ni 的情况。这种情况记 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]。在这两种决策中选择最优的即可。

dp[i][j]=min

代码 (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 + bb 可以进一步分解为 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,则将答案 reskp,将 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