[数据结构与算法]LeetCode-343. 整数拆分

LeetCode-343. 整数拆分

难度：中等
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

示例 :

输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

class Solution {
public:
    int integerBreak(int n) {
        vector<int> f(n+1);//f[i] 拆分数字i，使得f[i]为i拆分后的最大乘积的最大数
        f[1] = 1;
        for(int i=2;i<=n;i++){
            for(int j=1;j<=i/2;j++){
                /*
                    max(j*f[i-j] , j*(i-j))解释：我们f[i]存的值是数字i被拆分后的最大乘积，
                    但是在计算f[i+1]时有可能i>f[i],也就是不拆比拆了之后大，所以这里要求个最大值
                */
                f[i] = max(f[i],max(j*f[i-j] , j*(i-j)));

            }
        }
        return f[n];
    }
};

执行结果：
通过

执行用时：
0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：
6.1 MB, 在所有 C++ 提交中击败了52.21%的用户
通过测试用例：
50 / 50