343. Integer Break

Link

Solution

將答案分解成 dp[i] = dp[i-j] * dp[j]

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