題目

給定一個正整數(shù) n ，將其拆分為 k 個 正整數(shù) 的和（ k >= 2 ），并使這些整數(shù)的乘積最大化。

返回 你可以獲得的最大乘積 。

示例 1:

輸入: n = 2
輸出: 1
解釋: 2 = 1 + 1, 1 × 1 = 1。
示例 2:

輸入: n = 10
輸出: 36
解釋: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

提示:

2 <= n <= 58

解析

dp[i]的定義:分拆數(shù)字i可以得到的最大乘積為dp[i]
dp[i]的最大乘積可以通過2種方式得到：
第一種（2個數(shù)相乘）：
從1開始遍歷j，
j*(i-j)—會被多次調用
第二種(多個數(shù)相乘)
j*dp[i-j]

dp[i-j]為重疊子問題，會被多次調用比如

dp[5](dp[6-1],dp[7-2]...)dp[7]為dp[2]*dp[5]與dp[3]*dp[4]等的最大值

代碼

import java.util.Scanner;public class IntegerSplit {public static int integerBreak(int n) {int[] dp = new int[n+1];dp[2] = 1;for(int i = 3; i <= n; i++){for(int j = 1; j <= i; j++){dp[i] = Math.max(Math.max(j*(i-j), j*dp[i-j]),dp[i]);}}return dp[n];}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();System.out.println(integerBreak(n));}
}

dp數(shù)組中的每一個元素都是經過一個不斷擴大的循環(huán)計算出來的。