86整数拆分(343)

作者: Turbo时间限制: 1S章节: 动态规划

晚于: 2020-09-02 12:00:00后提交分数乘系数50%

截止日期: 2020-09-09 12:00:00

问题描述 :

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

示例 1:

输入: 2

输出: 1

解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: 10

输出: 36

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

输入说明 :

输入一个整数n

n 不小于 2 且不大于 58

输出说明 :

输出一个整数

输入范例 :

输出范例 :

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int integerBreak(int n) 
    {
        vector<int> dp(n+1,0);
        for(int i=2;i<=n;i++)
        {
            int cur=0;
            for(int j=1;j<i;j++)
            {
                cur=max(cur,max(j*(i-j),j*dp[i-j]));
            }
            dp[i]=cur;
        }
        return dp[n];
    }
};
int main()
{
    int n;
    cin>>n;
    int res=Solution().integerBreak(n);
    cout<<res;
}
/*
对于的正整数 nnn，当 n≥2n ge 2n≥2 时，可以拆分成至少两个正整数的和。令 kkk 是拆分出的第一个正整数，则剩下的部分是 n?kn-kn?k，n?kn-kn?k 可以不继续拆分，或者继续拆分成至少两个正整数的和。由于每个正整数对应的最大乘积取决于比它小的正整数对应的最大乘积，因此可以使用动态规划求解。
创建数组 dp	ext{dp}dp，其中 dp[i]	ext{dp}[i]dp[i] 表示将正整数 iii 拆分成至少两个正整数的和之后，这些正整数的最大乘积。特别地，000 不是正整数，111 是最小的正整数，000 和 111 都不能拆分，因此 dp[0]=dp[1]=0	ext{dp}[0]=	ext{dp}[1]=0dp[0]=dp[1]=0。
当 i≥2i ge 2i≥2 时，假设对正整数 iii 拆分出的第一个正整数是 jjj（1≤j<i1 le j < i1≤j<i），则有以下两种方案：


将 iii 拆分成 jjj 和 i?ji-ji?j 的和，且 i?ji-ji?j 不再拆分成多个正整数，此时的乘积是 j×(i?j)j 	imes (i-j)j×(i?j)；


将 iii 拆分成 jjj 和 i?ji-ji?j 的和，且 i?ji-ji?j 继续拆分成多个正整数，此时的乘积是 j×dp[i?j]j 	imes 	ext{dp}[i-j]j×dp[i?j]。


因此，当 jjj 固定时，有 dp[i]=max?(j×(i?j),j×dp[i?j])	ext{dp}[i]=max(j 	imes (i-j), j 	imes 	ext{dp}[i-j])dp[i]=max(j×(i?j),j×dp[i?j])。由于 jjj 的取值范围是 111 到 i?1i-1i?1，需要遍历所有的 jjj 得到 dp[i]	ext{dp}[i]dp[i] 的最大值，因此可以得到状态转移方程如下：
dp[i]=max?1≤j<i{max?(j×(i?j),j×dp[i?j])}	ext{dp}[i]=mathop{max}limits_{1 le j < i}{max(j 	imes (i-j), j 	imes 	ext{dp}[i-j])}
dp[i]=1≤j<imax?{max(j×(i?j),j×dp[i?j])}
最终得到 dp[n]	ext{dp}[n]dp[n] 的值即为将正整数 nnn 拆分成至少两个正整数的和之后，这些正整数的最大乘积。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/integer-break/solution/zheng-shu-chai-fen-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/