343.integer-break 整数拆分

题目描述

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];
        }
    }
};