/**
1. 动态规划
1.1 状态定义: f[i]为将i拆分后的最大乘积
1.2 状态计算: 以f[i] 为结尾考虑, 将 i 拆分为  i-j 和 j , 
    分解j: j 的最大成绩是f[j], 所以 f[i] = (i-j)*dp[j] 
    不分解j: f[i] = (i-j) * j
1.3 边界: f[0] = 0 , f[1] = 1


2. 数论:
2.1 求分解后的乘积最大 -> 看下什么时候分解乘积相等 
    2.1.1  3 = 1 + 2 > 1 * 2
    2.1.2  4 = 2 + 2 = 2 * 2
    2.1.3  5 = 2 + 3 < 2 * 3
    2.1.4  6 = 3 + 3 = 2 + 2 + 2 ; 3 * 3 > 2 * 2 * 2 > 1 * 2 * 3 > 1 * 5 

2.2 可以看出任何比3 大的数都能分解成 1 or 2 or 3 的乘积
    2.2.1 分解出1, 乘积会变小
    2.2.2 分解出3的结果比分解出2的大, 如果分解出>3 的数, 结果必定比分解出 2<= && <=3 的数小

2.3 所以尽量分解出更多的3
*/


class Solution {
    public int integerBreak(int n) {
        // return dp(n);
        return math(n);
    }

    public int math(int n){
        if (n <= 3) return n-1;
        int res = 1;
        for (; n %3 != 0; n-=2)  res *= 2;
        for (; n !=0 ; n-=3) res *= 3;
        return res;
    }

    public int dp(int n){
        int[] f = new int[n+1];
        f[1] = 1;
        for (int i = 2 ; i <= n; i++){
            for (int j = 1; j < i ;j ++){
                f[i] = Math.max(f[i],(i-j)*Math.max(f[j], j));
            }
        }
        return f[n];
    }
}