343. 整數拆分 劍指 Offer 14- II. 剪繩子 II

// 動态規劃 時間O(n*n)  空間 O(n)
public int integerBreak(int n) {
        int[] dp = new int[n+1];
        // dp[i]: i拆分成至少兩個正整數的和之後，最大的成績
        dp[0] = dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            int currMax = 0;
            for (int j = 1; j < i; j++) {
                currMax = Math.max(currMax, Math.max(j * (i-j), j * dp[i-j]))
            }
            dp[i] = currMax;
        }
        return dp[n];
    }

public int integerBreak(int n) {
        if(n <= 3) return n-1;

        long res = 1L;
        //貪心算法，優先切三，其次切二
        while (n > 4) {
            res *= 3;
            //res = res % 1000000007;
            n -= 3;
        }
        //出來循環隻有三種情況，分别是n=2、3、4
        //return (int)((res * n) % 1000000007);
        return (int)((res * n) );
    }