力扣题目聚合：https://leetcode-cn.com/problems/integer-break太平洋在线捕鱼

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

示例 1:

示例 2:

阐述: 你不错假定 n 不小于 2 且不大于 58。

看到这谈题目，齐会想拆成两个呢，仍是三个呢，仍是四个....

咱们来看一下如何使用动规来惩办。

动规五部曲，分析如下：

细则dp数组(dp table)以及下主义含义

dp[i]：分拆数字i，不错得到的最大乘积为dp[i]。

dp[i]的界说讲贯彻通盘解题经过，底下哪一步想不懂了，就想想dp[i]究竟暗意的是啥!

细则递推公式

不错想 dp[i]最大乘积是如何得到的呢?

其实不错从1遍历j，然后有两种渠谈得到dp[i].

一个是j * (i - j) 径直相乘。

皇冠体育

一个是j * dp[i - j]，至极于是拆分(i - j)，对这个拆分不睬解的话，不错追念dp数组的界说。

j是从1动手遍历，拆分j的情况，在遍历j的经过中其实齐计较过了。那么从1遍历j，比拟(i - j) * j和dp[i - j] * j 取最大的。递推公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));

也不错这样流露，j * (i - j) 是单纯的把整数拆分为两个数相乘，而j * dp[i - j]是拆分红两个以及两个以上的个数相乘。

若是界说dp[i - j] * dp[j] 亦然默许将一个数强制拆成4份以及4份以上了。

是以递推公式：dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j});

那么在取最大值的时候，为什么还要比拟dp[i]呢?

因为在递推公式推导的经过中，每次计较dp[i]，取最大的费力。

dp的运行化

不少同学应该猜忌，dp[0] dp[1]应该运行化几许呢?

有的题解里会给出dp[0] = 1，dp[1] = 1的运行化，但解释比拟牵强，主要仍是因为这样运行化不错把题目过了。

严格从dp[i]的界说来说，dp[0] dp[1] 就不应该运行化，也便是莫得真谛的数值。

拆分0和拆分1的最大乘积是几许?

这是无解的。

这里我只运行化dp[2] = 1，从dp[i]的界说来说，拆分数字2，得到的最大乘积是1，这个莫得任何异议!

细则遍历规章

细则遍历规章，先来望望递归公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));

dp[i] 是依靠 dp[i - j]的现象，是以遍历i一定是从前向后遍历，先有dp[i - j]再有dp[i]。

成列j的时候，是从1动手的。i是从3动手，这样dp[i - j]便是dp[2]刚巧不错通过咱们运行化的数值求出来。

是以遍历规章为：

for (int i = 3; i <= n ; i++) {     for (int j = 1; j < i - 1; j++) {         dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));     } } 

例如推导dp数组

例如当n为10 的时候，dp数组里的数值，如下：

整数拆分

以上动规五部曲分析终了，C++代码如下：

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((i - j) * j, dp[i - j] * j));             }         }         return dp[n];     } }; 

本题也不错用盘算，每次拆成n个3，若是剩下是4，则保留4，然后相乘，关联词这个论断需要数学解释其合感性!

我莫得解释，而是径直用了论断。感好奇的同学不错我方再去商议商议数学解释哈。

给出我的C++代码如下：

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;     } }; 

技巧复杂度：

空间复杂度：

本题掌捏其动规的尺度，就不错了，盘算的解法如实浅近，但需要罕有学解释，若是能语焉概略亦然不错的。

其实这谈题方针递推公式并不好想，况兼运行化的场地也很有肃穆，我在写本题的时候一动手写的代码是这样的：

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

在解释递推公式的时候，也不错解释通，dp[i] 就等于 拆解i - j的最大乘积 * 拆解j的最大乘积。看起来没弱点!

关联词在解释运行化的时候，就发现鬻矛誉盾了，dp[1]为什么一定是1呢?字据dp[i]的界说，dp[2]也不应该是2啊。

但若是递归公式是 dp[i] = max(dp[i], dp[i - j] * dp[j]);，就一定要这样运行化。递推公式没弱点，但运行化解释欠亨!

天然代码在运行位置有一个判断if (n <= 3) return 1 * (n - 1);，保证n<=3 效用是正确的，但代码背面又要给dp[1]赋值1 和 dp[2] 赋值 2，这其实便是鬻矛誉盾的代码，抵触了dp[i]的界说!

我举这个例子，其实就说作念题的严谨性，上头这个代码也不错AC，大体上一看能够也莫得弱点，递推公式也说得畴前，关联词只是是恰巧过了费力。

Java

class Solution {     public int integerBreak(int n) {         //dp[i]为正整数i拆分效用的最大乘积         int[] dp = new int[n+1];         dp[2] = 1;         for (int i = 3; i <= n; ++i) {             for (int j = 1; j < i - 1; ++j) {                 //j*(i-j)代表把i拆分为j和i-j两个数相乘                 //j*dp[i-j]代表把i拆分红j和接续把(i-j)这个数拆分，取(i-j)拆分效用中的最大乘积与j相乘                 dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));             }         }         return dp[n];     } } 

Python

class Solution:     def integerBreak(self, n: int) -> int:         dp = [0] * (n + 1)         dp[2] = 1         for i in range(3, n + 1):             # 假定对正整数 i 拆分出的第一个正整数是 j（1 <= j < i），则有以下两种决策：             # 1) 将 i 拆分红 j 和 i−j 的和，且 i−j 不再拆分红多个正整数，此时的乘积是 j * (i-j)             # 2) 将 i 拆分红 j 和 i−j 的和，且 i−j 接续拆分红多个正整数，此时的乘积是 j * dp[i-j]             for j in range(1, i - 1):                 dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))         return dp[n] 

Go

func integerBreak(n int) int {     /**     动态五部曲     1.细则dp下标偏执含义     2.细则递推公式     3.细则dp运行化     4.细则遍历规章     5.打印dp     **/     dp:=make([]int,n+1)     dp[1]=1     dp[2]=1     for i:=3;i<n+1;i++{         for j:=1;j<i-1;j++{ // i不错差分为i-j和j。由于需要最大值，故需要通过j遍历所有存在的值，取其中最大的值四肢现时i的最大值，在求最大值的时候，一个是j与i-j相乘，一个是j与dp[i-j].             dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]))         }     }     return dp[n] } func max(a,b int) int{     if a>b{         return a     }     return b } 

Javascript

var integerBreak = function(n) {     let dp = new Array(n + 1).fill(0)     dp[2] = 1      for(let i = 3; i <= n; i++) {         for(let j = 1; j < i; j++) {             dp[i] = Math.max(dp[i], dp[i - j] * j, (i - j) * j)         }     }     return dp[n] };