算法动态规划

使得乘积最大的整数分拆：基于数学性质对决策空间剪枝

字数统计: 1.8k字   |   阅读时长: 7分
, , , , , ,

摘要: 动态规划解决数列第 n 项问题

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

整数分拆问题是组合数学中的一个经典问题，它涉及到将一个整数分拆成若干个较小整数的和的不同方式。常规的整数分拆问题问的是有多少种分拆方法，具体分为无序分拆和有序分拆两种类型，是一种组合计数问题。

本文我们看一下在整数的无序分拆的所有方法中，分拆出的各个数可以取到的最大乘积是多少，这是组合优化的问题。

通过本题，我们重点看一下如何通过发现数学性质排除掉无效的决策，降低状态转移的时间复杂度。

使得乘积最大的整数分拆问题

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

示例 1:
输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:
输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

提示:

1
2 <= n <= 58

算法：动态规划

比较直接的想法是定义 $dp[i]$ 表示 $i$ 分拆成若干个整数之和可以取到的最大乘积。阶段要素是已经分拆出的数字的个数，$i$ 是作为附加信息出现在 DP 状态中。这样定义的话，答案为 $dp[n]$。

初始值就是 $dp[2] = 1$，原因在于 $2$ 拆分成至少两个数只有 $2 = 1 + 1$ 这一种，另外对于 $3$，如果拆分成至少 2 个数，最好的拆法为 $3 = 2 + 1$，这样乘积为 2，因此 $dp[3] = 2$ 也是一个初始值。

下面考虑状态转移方程。对于数 $i$，至少分拆为 2 个数，则所有 $2$ 到 $i-2$ 范围的数字都是有可能作为拆出的数的，需要 $dp[2], \cdots, dp[i -2]$ 都推导完了，才能推导 $dp[n]$。因此状态推导顺序就是 $i$ 从小到大的顺序即可，这是线性 DP。

假设当前推导到 $dp[i]$，如果拆出一个数字 $k (2 \leq k \leq i - 2)$，则对应的决策为 $k \times dp[i - k]$，但注意，这里 $dp[i - k]$ 记录的是把 $i - k$ 分拆成至少 2 个数所得的最大乘积。而对 $dp[i]$ 来说，$k$ 已经是一个数了，$i - k$ 也可以不分拆。

综合起来，状态转移方程如下：

共 $n$ 个状态，每个状态在转移时需要 $O(n)$，因此总时间复杂度为 $O(n^{2})$。

代码 (C++)

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

优化：排除无效决策DP

对于 $i$，如果 $i = 4$，则 $k$ 只能取 2，对应得到 $dp[4] = 4$，把该状态也作为初始值。状态转移方程从 $i = 5$ 开始考虑。

当 $i \geq 5$ 时，$k$ 在 $2, 3, \cdots, i-2$ 这些可能的决策中，直接取 $k=3$ 作为最优决策，转移到 $3dp[i-3]$ 即可。下面说明这样选取最优决策的正确性。

引理1

当 $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$

引理2

当 $i \geq 4$ 时，执行分拆会取得更好的结果。

证明

$i \geq 4$ 时，不妨设执行的分拆为 $i = a + b$，其中 $a, b \geq 2$。由引理1，$ab \geq a + b = i$。

因此执行分拆会取到更好的结果。

$\Box$

引理3

$i \geq 5$ 时，$k$ 取 3 可以取到最优结果。

证明

由引理2，只要 $i \geq 4$，就执行分拆。因此 $i$ 拆成的若干个数中，只要有哪个数大于等于 $4$，就对该数继续分拆，直至所有的数都小于 $4$。

因此 $i \geq 4$ 的最终的最优分拆中，只含有若干个 2 和若干个 3。

考虑 $2$ 的个数 $k_{2}$，若 $k_{2} \geq 3$，则把 3 个 $2$ 改成 2 个 $3$，所得乘积 $9$ 大于改之前的 $8$。

因此只要 $k_{2} \geq 3$ 就不断把 3 个 $2$ 改为 2 个 $3$，直至 $2$ 的个数小于 3。

综上，$i \geq 4$ 时，最优分拆为最多 2 个 $2$ 加上若干个 3。

2 个 $2$ 能贡献的和为 4，因此当 $i \geq 5$ 时，就必须有 $3$ 才能拆成最多 2 个 $2$ 加上若干个 3 的形式。

因此 $i \geq 5$ 时，直接取 $k = 3$ 作为最优决策即可。

$\Box$

引入上述策略直接选取最优决策之后，决策可以 $O(1)$，因此总时间复杂度变为 $O(n)$。

代码 (C++)

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

算法：贪心

根据前面的选取最优决策的方法，$n$ 最终的最优分拆为 $n = 2a + 3b$，即 $a$ 个 2 和 $b$ 个 3。其中 $0 \leq a \leq 2$。

$a = 0$ 对应 $3$ 能整除 $n$ 的情况，此时有 $\frac{n}{3}$ 个 3，答案为 $3^{\frac{n}{3}}$。

$a = 1$ 对应 $n$ 模 3 余 2 的情况，此时有 1 个 2 和 $\frac{n - 2}{3}$ 个 3，答案为 $2 \times 3^{\frac{n - 2}{3}}$；

$a = 2$ 对应 $n$ 模 3 余 1 的情况，此时有 2 个 2 和 $\frac{n - 4}{3}$ 个 3，答案为 $4 \times 3^{\frac{n - 4}{3}}$。

这样从 $n$ 就可以直接推出结果了。

求 $3$ 的幂次用快速幂，总时间复杂度可以做到 $O(\log n)$。

代码 (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
32
33
34
35
using ll = long long;

ll quickpower(ll a, ll n)
{
    // a==0 && n==0 特判
    ll ans = 1; // n = 0 时候不进循环
    while(n)
    {
        if(n & 1) 
            ans *= a;
        a *= a;
        n >>= 1;
    }
    return ans;
}

class Solution {
public:
    int integerBreak(int n) {
        if(n <= 3) 
            return 1 * (n - 1);
        if(n % 3 == 0)
        {
            return quickpower(3, n / 3);
        }
        else if(n % 3 == 2)
        {
            return 2 * quickpower(3, (n - 2) / 3);
        }
        else
        {
            return 4 * quickpower(3, (n - 4) / 3);
        }
    }
};
Share