递归解法

class Solution {
public:
    int integerBreak(int n) {
        if(n <= 2) return 1;
        int ans = INT_MIN;
        for(int i = 2;i < n;i++)
        {
            int product = i * max(n-i,integerBreak(n-i));
            if(product > ans)
                ans = product;
        }
        return ans;
    }
};

运行结果:

Time Limit Exceeded
Details 
Last executed input
43

这里的套路就非常熟悉了，引入记忆化即可。从顶向上计算，需要是递归。

class Solution {
public:
    int integerBreak(int n) {
        vector<int> mem(n+1,-1);
        return helper(n,mem);
    }
private:
    int helper(int n,vector<int>& mem){
        if(n <= 2) return 1;
        int ans = INT_MIN;
        if(mem[n] != -1)
            return mem[n];
        for(int i = 2;i < n;i++)
        {
            int product = i * max(n-i,helper(n-i,mem));
            if(product > ans)
                ans = product;
        }
        mem[n] = ans;
        return ans;
    }
};

运行效率：

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Integer Break.
Memory Usage: 6.2 MB, less than 9.92% of C++ online submissions for Integer Break.

方法二：从底向上，迭代计算结果：

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

运行效率:

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Integer Break.
Memory Usage: 6.2 MB, less than 34.50% of C++ online submissions for Integer Break.

视频题解参考