leetcode 343. 整數拆分 & leetcode 劍指 Offer 劍指 Offer 14- I. 剪繩子

343. 整數拆分

思路一：動态規劃

一個整數被拆分成 k  和 (n-k)後，可以把(n-k)繼續往下拆分，也可以選擇不繼續往下拆分，是以整數 n 被拆分後得到的乘積最大值就是 k*(n-k) 或者 k*(n-k被拆分後得到的乘積最大值)。由于每個正整數對應的最大乘積取決于比它小的正整數對應的最大乘積，是以可以使用動态規劃求解。

令dp[i] 表示把正整數 i 拆分成至少兩個整數後，這些正整數的最大乘積。特别地，0 不是正整數，1 是最小的正整數，0和 1 都不能拆分，是以dp[0]=dp[1]=0。

當i≥2 時，假設對正整數 ii 拆分出的第一個正整數是(1≤j<i），則有以下兩種方案：

• 将 i 拆分成 j 和 i−j 的和，且i−j 不再拆分成多個正整數，此時的乘積是 j×(i−j)；
• 将 i 拆分成 j 和i−j 的和，且 i−j 繼續拆分成多個正整數，此時的乘積是 j×dp[i−j]。

1 class Solution {
 2     public int integerBreak(int n) {
 3         int[] dp = new int[n + 1];
 4 
 5         for(int i = 2; i <= n; i++){
 6             int temp = 0;
 7             for(int j = 1; j < i; j++){
 8                 temp = Math.max(temp, Math.max(j * (i - j), j * dp[i - j]));
 9             }
10             dp[i] = temp;
11         }
12         return dp[n];
13     }
14 }      

執行用時：1 ms, 在所有 Java 送出中擊敗了62.23%的使用者

記憶體消耗：34.8 MB, 在所有 Java 送出中擊敗了99.04%的使用者

思路二：

思路參考：https://leetcode-cn.com/problems/integer-break/solution/343-zheng-shu-chai-fen-tan-xin-by-jyd/

根據數學證明，當一個數被拆分成盡可能多的3的時候，所有因子的乘積是最大的。是以我們應該盡可能把每段的長度控制為3， 看最多能拆成多少個3,但是如果n / 3不等于0， 代表該整數不能被3整除，這時需要特别判斷一下：

如果餘數為0， 最大乘積就是所有3的乘積

1 class Solution {
 2     public int integerBreak(int n) {
 3         if(n <= 3){
 4             return n - 1;
 5         }
 6         int a = n / 3;
 7         int b = n % 3;
 8         if(b == 0){
 9             return (int)Math.pow(3, a);
10         }else if(b == 1){
11             return (int)Math.pow(3, a - 1) * 4;
12         }else{
13             return (int)Math.pow(3, a) * 2;
14         }
15     }
16 }