题目描述 链接到标题

343.整数拆分

解题思路 链接到标题

还是寻找递推关系,设$dp_n$为正整数$n$所求的最大乘积。 这里可以注意到:$n > 4$时， $dp_n = \max[dp_{n - 3} * 3,\ dp_{n - 4} * 4]$。 根据递推关系写出for循环递推求解。

代码 链接到标题 

class Solution {
  public:
    int get_max(int a, int b) {
        return a > b ? a : b;
    }
    int integerBreak(int n) {
        vector<int> res(n);
        if (n == 1 || n == 4)
            return n;
        else if (n == 2 || n == 3)
            return 1 * (n - 1);
        else {
            for (int i = 0; i < 4; i++)
                res[i] = i + 1;
            for (int i = 4; i < n; i++) {
                res[i] = get_max(res[i - 3] * 3, res[i - 4] * 4);
            }
            return res[n - 1];
        }
    }
};