[leetcode]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.

题目很简单，给个 n，所有和为 n 的数的乘积的最大值。

比如 10 = 5 + 5 -> 5*5=25
             3+3+4->3*4*4=26

一看想法就是动态规划，状态也很好划分

     f[n] 表示数字为 n 时的最优值
     那么 f[n] = max(i, f[i]) * max(j * f[j]) 其中 i + j == n

为什么要 max(f, f[i]) 这样呢，因为有时候我们划分了反而没有这个数本身大，比如f[3] = 2，那我们计算到3的时候，就不要去用f[3]了，ok，代码也很短

class Solution {
public:
    int integerBreak(int n) {
        vector<int> f(n + 1, 0);
        f[1] = 0;
        f[2] = 1;
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                f[i] = max(f[i], max(f[j], j) * max(f[i - j], i - j));
            }
        }
        return f[n];
    }
};