题目

integer-break

2. 算法

* 直接模拟

* 优化

3. 代码

* 直接模拟

class Solution {

public:

    int integerBreak(int n) {

        if (n == 2 || n == 3) return n - 1;

        int res = 1;

        while (n > 4) {

            res *= 3;

            n -= 3;

        }

        return res * n;

    }

};

* 优化

class Solution {

public:

    int integerBreak(int n) {

        vector<int> dp{0, 0, 1, 2, 4, 6, 9};

        for (int i = 7; i <= n; ++i) {

            dp.push_back(3 * dp[i - 3]);

        }

        return dp[n];

    }

};