Leetcode解题报告——343. Integer Break

题目要求:
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.

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

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

大意:
给定一个正整数 n，把它拆分为至少2个正整数，并使得它们的乘积最大，返回最大乘积

示例:

输入     n : 2  3  4  5  6  7  8   9
输出 result: 1  2  4  6  9  12 18 27

这种输入整数求某种值，比如我们上篇讲的Counting Bits 的解题思路首先要把一些例子写出来，然后再找输入、输出与前面的输入、输出之间的规律即可。
对于这道题，假设输入 n 为9。则 9 可拆分为 7和2、6和3、5和4。9对应的输出一定是这些组合里面的最大值。

7和2 ： max_value = max(7,12) * max(2,1) // 7 可以取值 7 ，也可以取它对应的输出12
6和3 ： max_value = max(6,9)  * max(3,2)
....

根据上述思路，我们很容易得出源码。

public  int integerBreak(int n) {
        int []dp = new int[n+1];
        dp[1] = 1;
        
        for (int i = 2; i <=n ; i++) {
            for (int j = i-1; j >=i/2 ; j--) {
                dp[i] = Math.max(dp[i],Math.max(j,dp[j])*Math.max(i-j,dp[i-j]));
            }
        }
        return dp[n];
    }