Question

Given a positive integer n, break it into the sum of at least two positive integers and maximize the PRoduct of those integers. Return the maximum product you can get.

Note: You may assume that n is not less than 2 and not larger than 58.

給出一個正整數(shù)n，把它分解為至少兩個正整數(shù)，使這些正整數(shù)之積最大。返回最大的積。(2 <= n <= 58)

Example

For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

Solution

動態(tài)規(guī)劃解。定義dp[i]：將i分解得到的最大的積。遞推式：dp[i] = max(dp[i - j] * j, (i - j) * j) (j < i)。因為至少分解兩個整數(shù)，所以dp[i]并不包含分解的值本身，即(i - j) * j，因此我們需要比較它們的大小。假設(shè)i = 4，如果我們分解出1，那么max（dp[3] * 1，3 * 1）就是分解出1時的最大積了，然后我們只需分別求出分解出2， 3的最大積，其中最大的積就是dp[4]了