2017-10-08 15:58:04 +0000   |     algorithm leetcode math dynamic programming   |   Viewed times   |    

题目

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.

自底向上的动态规划

递归式如下,

T(n) = MAX( MAX(2,T(2)) * MAX(n-2),T(n-2)), MAX(3,T(3)) * MAX(n-3),T(n-3)), MAX(4,T(4)) * MAX(n-4),T(n-4)), … … MAX(n/2,T(n/2)) * MAX(n-n/2,T(n-n/2)) )

需要注意,[2,3,4]3个数字是特例,他们的最大积小于他们本身。所以可以将他们预设为基础解。

代码

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

结果

integer-break-1

数学规律

仔细观察,可以发现所有分解出来的最优解都是由23两个因数组成,再具体一点,

取尽可能多的3,直到余下2时取一个2,余下4时取两个2.

原理是因为两个数因数分解,总是当两个因数相等的时候,积最大。

但这就导致只要当(N/2)*(N/2)>=N的时候,继续往下分解总能得到更优的解。那这个界限在哪儿呢?就是我们上面发现的4

所以分解出来的因数不可能超过4,其中1又没有意义,所以只有两个可能的因数[2,3]

最后为什么尽可能多地取3而不是2呢?一个直观的例子就是63*3 > 2*2*2,所以3更给力那么一点。唯一23强的地方是2*2 > 1*3,所以只需要注意在余数为4的时候,取2*2即可。

所以最后

代码

class Solution {
    public int integerBreak(int n) {
        if (n == 2) { return 1; }
        if (n == 3) { return 2; }
        int product = 1;
        while (n > 4) {
            product *= 3;
            n -= 3;
        }
        return product * n;
    }
}

结果

integer-break-2