// @Title: 整数拆分 (Integer Break)
// @Author: qisiii
// @Date: 2024-09-23 00:03:27
// @Runtime: 2 ms
// @Memory: 39.3 MB
// @comment: 
// @flag: 
class Solution {
    public int integerBreak(int n) {
        int[] dp=new int[n+1];
        dp[2]=1;
        for(int i=3;i<=n;i++){
            for(int j=1;j<i-1;j++){
                //Max(j*(i-j),dp[j]*(i-j),dp[j]*dp[i])
                dp[i]=Math.max(dp[i],Math.max(j*(i-j),Math.max(dp[j]*(i-j),dp[j]*dp[i-j])));
            }
        }
        return dp[n];
    }
}