LeetCode 343 整数拆分

343.整数拆分

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

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

动态规划

此处使用动态规划求解，首先需要确定的是问题的划分，对于整数 n 拆分的方式存在多种 1+n-1 或 2+n-2 ，同时也可以进一步对 n-1 和 n-2 进行拆分，此处使用一个动态规划数组 dp[i] 来表示，将数字 i 拆分为任意份后能够得到的最大乘积，那么对于数字 n 的拆分为 和 的情形最大乘积求解存在三种情况：

1. 两个值都拆分的情形 在此基础上将 和 进一步拆分为多个值的最大值 。

2. 两个值都不进行拆分的情况： 两个值都不进行拆分，那么

3. 两个值一个拆分，另一个不拆分： 对 进行拆分 $n^3_{最大乘积}=dp[n-i]iin^4_{最大乘积}=(n-i)dp[i]$

在此基础上得到递推公式为：

$$dp[n]=max(max_{i}(n^1_{最大乘积},n^2_{最大乘积},n^3_{最大乘积},n^4_{最大乘积}))$$

其中

在上述基础上使用动态规划求解：

1. 确定动态规划数组及其含义：使用长度为 n 的动态规划数组 dp[n+1] 其中 dp[i] 表示数字 i 对应的最大乘积值

2. 确定递推公式： 其中

3. 动态规划数组的初始化： dp[0]=0，dp[1]=0

4. 动态规划数组的遍历顺序：在推导 dp[i] 时，需要使用到前述的前部元素，从前向后推导。

5. 举例实现： n=3 那么 dp[2]=max(max(dp[1]*dp[1],1*1,dp[1]*1,1*dp[1]))=1 ，再计算 dp[3]=max(max(dp[2]*dp[1],2*1,dp[2]*1,2*dp[1]))=2 ，计算正确。

代码实现：

class Solution {
public:
    int getDp(const vector<int> &dp,int i){
        int res=0,tmp;
        for(int j=1;j<=i/2;j++){
            tmp=max(dp[i-j]*dp[j],(i-j)*j);
            tmp=max(dp[i-j]*j,tmp);
            tmp=max((i-j)*dp[j],tmp);
            res=max(res,tmp);
        }
        return res;
    }
    int integerBreak(int n) {
        vector<int> dp(n+1,0);
        for(int i=2;i<=n;i++){
            dp[i]=getDp(dp,i);
        }
        return dp[n];
    }
};

此处的拆分的情况还可以进行进一步的合并：对于两个数都拆分和两个数中仅拆分一个实际上是相同的。对于数字 在 的情况下，此处的要令 ，每次只需要对 进行拆分即可实现全部情况的涵盖。当 时，仅对 拆分，实际上就计算了拆分数值包含1的全部情况，当 时，仅对 拆分，就计算的拆分数值包含2的全部情况。依次类推即可在在两种情况下完成计算。

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n+1,0);
        for(int i=2;i<=n;i++){
            for(int j=1;j<i;j++){
                dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]));
            }
        }
        return dp[n];
    }
};