343. Integer Break

Given a positive integer n, break it into the sum of k positive integers (k >= 2) and maximzie the product of those integers. Return the maximum product you can get.

Example 1:

Input: n = 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

Input: n = 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Constraints: 2 <= n <= 58

Solution

Mathematical Approach

The optimal strategy is to break n into as many 3's as possible, but if the remainder is 4, keep it as 4 (since 3×1 < 2×2).

class Solution {
    public int integerBreak(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;
        int quotient = n / 3;
        int remainder = n % 3;
        if (remainder == 0) {
            return (int) Math.pow(3, quotient);
        } else if (remainder == 1) {
            return (int) Math.pow(3, quotient - 1) * 4;
        } else { // remainder == 2
            return (int) Math.pow(3, quotient) * 2;
        }
    }
}

Dynamic Programming Approach

Define dp[i] as the maximum product for integer i. For each i, we split it into j and i-j and compare three values: dp[i-j] * j, j * (i-j), and the current dp[i].

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 / 2; j++) {
                dp[i] = Math.max(dp[i], Math.max(dp[i - j] * j, j * (i - j)));
            }
        }
        return dp[n];
    }
}

96. Unique Binary Search Trees

Given an integer n, return the number of structurally unique BSTs (binary search trees) which have exactly n nodes of unique values from 1 to n.

Example 1:

Input: n = 3
Output: 5

Example 2:

Input: n = 1
Output: 1

Constraints: 1 <= n <= 19

Solution

Let dp[i] be the number of BSTs with i nodes. For each root j (from 1 to i), the left subtree has j-1 nodes and the right subtree has i-j nodes. Thus, dp[i] = sum_{j=1}^{i} dp[j-1] * dp[i-j].

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}