Integer Break

LeetCode 343.

1
2
3
4
5
6
7
8
9
10
public int integerBreak(int n) {
    int[] dp = new int[n + 1];
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= i - 1; j++) {
            dp[i] = Math.max(dp[i], Math.max(j * dp[i - j], j * (i - j)));
        }
    }
    return dp[n];
}

Mathematical solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int integerBreak(int n) {
     if(n <=3){
         return n -1; 
     }

     int a = n/3;
     int b = n % 3; //b 只能为 0  1   2 
     //b == 1
     if(b == 1){
        return (int)Math.pow(3,a - 1) * 4;
     }else if (b == 2){
        return (int)Math.pow(3,a) * b;
     }else{
        return (int)Math.pow(3,a);
     }

    }
}