【力扣343】整数拆分_整数拆分如何计算

这里讲述这道题的两道解法，一种是动态规划，一种是贪心算法，后者的时间复杂度和空间复杂度都更小。
原题：
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。

提示：2 <= n <= 58

一.动态规划解法

1. 确定dp数组以及下标的含义

假设要拆分数字i，拆分后可以得到的最大乘积为dp[i]

2. 确定递推公式

将数数字从1遍历到j，j小于i，如果拆分成两部分，那dp[i] 就为 j * (i - j)最大时的情况

如果拆分成两份以上，那dp[i] 就是j * dp[i - j]

dp[i]为两者取最大，max(j * (i - j)，j * dp[i - j])

又因为dp[i]一直在更新，可能前面的dp[i]比后面更大，所以得把dp[i]也算上(因为j在变，上一个j时的dp[i]可能比现在的dp[i]大，尽管在内for循环里i没变)

即dp[i] = max(dp[i], max(j * (i - j), dp[i - j]))

3. dp数组的初始化

dp[0]和dp[1]没有意义，无法拆分，且提示里说：2 <= n <= 58

所以初始化dp[2] = 1

4. 遍历顺序

后面的dp[i]依赖前面的dp[i - j]结果，所以得从前往后遍历

且i - j >= 2，j >= 1，没有dp[j]，所以j可以从1开始遍历，为满足i - j >= 2，i得从3开始遍历

5. 举例推导dp数组

要注意一下dp数组的初始化问题，因为这里，dp[i] = max(dp[i], max(j * (i - j), dp[i - j]))右边dp[i]的初值如果由编译器随机设定，可能会很大，使得dp[i]最终max后取得是初值，而不是实际值。
一方面，普通数组的大小必须的固定的值，像函数形参这种就是不固定的值，所以代码随想录里就用的vector容器，而我一开始用普通数组，如int dp[n + 1]则出错，因为n是不固定的，是函数形参，在变化，导致不能初始化int dp[n + 1] = {0}也报错，但是int dp[60] = {0}不会，如果不初始化，而是默认初始化。则会出现整型溢出的情况

上面这种做法不仅违背普通数组大小固定大小的原则，而且没有指定初始化为0或其它小数，被随机初始化了，所以才会出现2106525680这么大的数，如下，即使定义为dp[60]但不指定初始化为0或者1这种小数，也会出错。


正确代码：

class Solution {
public:
    int integerBreak(int n) {
        int dp[60] = {0};//普通数组需要大小固定，且初始化为0最好，vector容器可以动态扩容且构造函数将所有元素默认初始化为0
        //所以可以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(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

二. 贪心算法

主要是根据数学证明，一个大于4的 数拆分成各个整数相乘时，出现最大乘积的情况是这样的：
分成3 x 3 x …直到没有3，不过，如果剩下的是4，也不能拆分成3 + 1，这样就乘以3了，而是保留4，因为乘以4自己会更大

所以贪心就是一直取3，直到n只剩4及以下的情况

例如剩余4，那就乘4而不是x3 x 1，剩余3肯定是x3，剩余2也是x2。

小于等于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;//和取完3剩下的数如4,3,2相乘
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时间复杂度从动规的O(n^2)优化到O(n)

空间复杂度从动规的O(n)优化到O(1)，

但是力扣运行结果居然贪心比动规还耗时，内存消耗也和动规差不多！

应该是n太小，多次if判断语句显得更耗时