Integer Partition Problem

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers.

Approach

We use dynamic programming where dp[i] represents the maximum product for integer i. The key insight is that for each integer i, we can break it into j and i-j, then consider three cases:

1. Direct multiplication of j and (i-j)
2. Using the previously computed maximum product for j
3. Using the previously computed maximum product for (i-j)

Solution Code

vector<int> maxProductPartition(int n) {
    vector<int> dp(n + 1, 0);
    dp[2] = 1;
    
    for (int num = 3; num <= n; ++num) {
        for (int split = 1; split <= num / 2; ++split) {
            int current = max(split * (num - split), 
                             split * dp[num - split]);
            dp[num] = max(dp[num], current);
        }
    }
    return dp;
}

Unique Binary Search Trees Problem

Givan an integer n, return the number of structurally unique BSTs that store values 1 to n.

Approach

We use dynamic programming where dp[i] represents the number of unique BSTs for i nodes. The solution relies on the Catalan number formula, where each dp[i] is the sum of products of dp[j-1] and dp[i-j] for all possible roots j.

Solution Code

vector<int> countBSTs(int n) {
    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    
    for (int nodes = 1; nodes <= n; ++nodes) {
        for (int root = 1; root <= nodes; ++root) {
            dp[nodes] += dp[root - 1] * dp[nodes - root];
        }
    }
    return dp;
}