动态规划3--分割整数

343. 整数拆分

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例 1:

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

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

说明: 你可以假设 *n *不小于 2 且不大于 58。

分析：好难呐~~~
根本没有状态转移方程的思路5555~

动态规划五部曲：
1、确定dp数组以及下标含义
dp[i]表示整数i对应的最大乘积，不论拆成几部分。

2、确定状态转移方程

• 如果整数i拆分成两部分(j,i-j)，那么乘积为 j×(i−j)；
• 如果整数i拆分成多个部分，可以看做把它拆分成两部分，其中一个部分又进行了拆分（不要同时拆分两部分）。进行拆分的那一部分，他的乘积为dp[i-j]，所以乘积是 j×dp[i−j];

3、dp数组的初始化
拆分成0*n时，乘积为0，初始化dp[]={0};

4、确定遍历的顺序
略
5、举例检验
略

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/2+1;j++)
            {
                dp[i]=max({dp[i],j*(i-j),(j)*dp[i-j]});
            }
        }
        return dp[n];
    }
};

• 将 i 拆分成 j 和 i−j的和，且 i−j不再拆分成多个正整数，此时的乘积是 j×(i−j)；

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

时间复杂度：O(n^2)；空间复杂度：O(n)