力扣：343. 整数拆分

力扣：343. 整数拆分

题目：
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。

思路：
首先思考这是一个动态规划的题目，那么当前值是由前面的值表示出来的，怎么表示呢?不清楚。此时就应该通过答案反推过程同时在此过程中要始终记得当前值是可以由前面的值表示的。一个值被拆分成几个值，同时有这种情况：

1. dp[ n ] = 某某+dp[ i ]
2. dp[ i] = 某某+dp[ i] +/-/*/÷ dp[ j ]
3. 等等

此时可以联想到求dp[ i ] 有以下两种方案：

将 i 拆分成 j 和 i−j 的和，且 i−j 不再拆分成多个正整数，此时的乘积是 j * i-j

将 i 拆分成 j 和 i−j 的和，且 i−j 继续拆分成多个正整数，此时的乘积是 j * dp[ i-j ]

因此，当 j 固定时，有 dp[ i ] = max( j × ( i−j ) , j × dp[ i−j ])。
由于 j 的取值范围是 1 到 i-1，所以需要遍历所有的 j 得到 dp[ i ] 的最大值

动态规划代码：

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

贪心：
本题也可以用贪心，每次拆成n个3，如果剩下是4，则保留4，然后相乘，但是这个结论需要数学证明其合理性！
我没有证明，而是直接用了结论。感兴趣的同学可以自己再去研究研究数学证明哈。

class Solution {
public:
    int integerBreak(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;
        if (n == 4) return 4;
        int result = 1;
        while (n > 4) {
            result *= 3;
            n -= 3;
        }
        result *= n;
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15