343. Integer Break

[w4irdo]

# 动态规划
class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j < i; j++)
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), dp[j] * (i - j)));
        return dp[n];
    }
}

# 贪心
class Solution {
    public int integerBreak(int n) {
        if (n < 2)
            return 0;
        if (n == 2)
            return 1;
        if (n == 3)
            return 2;
        int timeOf3 = n / 3;
        if (n - timeOf3 * 3 == 1)
            timeOf3--;
        int timeOf2 = (n - timeOf3 * 3) / 2;
        return (int) (Math.pow(3, timeOf3)) * (int) (Math.pow(2, timeOf2));
    }
}