Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 343. Integer Break

---

題目：


方法：

盡量拆成3，因為最佳拆分接近3

解答一：

class Solution {
public:
    int integerBreak(int n) {
        if (n <= 3) {
            return n - 1;
        }

        int ans = 1;
        while (n > 4) {
            ans *= 3;
            n -= 3;
        }

        return ans * n;
    }
};

方法：

dp[i] = max(
    j * (i - j),    // 拆成兩段
    j * dp[i - j]   // 繼續拆
)

解法二：

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n + 1, 0);

        dp[1] = 1;
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j < i; ++j) {
                dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]));
            }
        }

        return dp[n];
    }
};