343. Integer Break

把一个整数分成至少两份，找出它们乘积最大值

1.递归：

public int integerBreak(int n) {
    if (n == 1) return 1;
    int res = 0;
    for (int i = 1; i < n; i++) {
        res = Math.max(Math.max(res, i * (n - i)), i * integerBreak(n - i));
    }
    return res;
}

2.memo:

int[] memo;
public int integerBreak(int n) {
    memo = new int[n + 1];
    Arrays.fill(memo, -1);
    ib(n);
    return memo[n];
}

public int ib(int n) {
    if (n == 1) return 1;
    if (memo[n] != -1) return memo[n];
    int res = 0;
    for (int i = 1; i < n; i++) {
        res = Math.max(Math.max(i * ib(n - i), i * (n - i)), res);
    }
    memo[n] = res;
    return res;
}

递归树：

3.dp:

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

其中i,j变量的含义：