Integer Partitioning for Maximum Product

To maximize the product of integers summing up to a target value n, dynamic programming tracks optimal sub-solutions. Define an array maxProduct where maxProduct[val] represents the highest achievable product from partitioning the integer val.

Since partitioning 0 or 1 yields no valid product, the base case starts at val = 2, where the only valid split is 1 + 1, giving maxProduct[2] = 1.

For any integer val greater than 2, it can be split into two components: a left part split and a remaining part val - split. Two scenarios arise for this remaining part:

• It is not partitioned further, resulting in a product of split * (val - split).
• It is partitioned recursively, yielding a product of split * maxProduct[val - split].

The optimal product for val is the maximum across all possible splits. A split only needs to iterate up to val / 2 due to the symmetric nature of multiplication. During iteration, maxProduct[val] must continuously compare and update against its current value, the un-partitioned product, and the recursively partitioned product.

class Solution {
public:
    int integerBreak(int n) {
        std::vector<int> maxProduct(n + 1, 0);
        maxProduct[2] = 1;
        
        for (int val = 3; val <= n; ++val) {
            for (int split = 1; split <= val / 2; ++split) {
                int unpartitioned = split * (val - split);
                int partitioned = split * maxProduct[val - split];
                maxProduct[val] = std::max({maxProduct[val], unpartitioned, partitioned});
            }
        }
        return maxProduct[n];
    }
};

Counting Unique Binary Search Trees

The count of structurally unique Binary Search Trees (BSTs) that can be formed with nodeCount nodes depends on the structural combinations of left and right subtrees. Let treeCounts[nodeCount] denote the number of unique BSTs possible with nodeCount nodes.

An empty tree counts as a valid structure, so treeCounts[0] = 1. A single node also forms exactly one BST, hence treeCounts[1] = 1.

For nodeCount > 1, each node root from 1 to nodeCount can serve as the root. If root is chosen, the left subtree contains root - 1 nodes, and the right subtree contains nodeCount - root nodes. The total BSTs with root at the head equals the product of possibilities for both subtrees: treeCounts[root - 1] * treeCounts[nodeCount - root]. Summing this product across all possible roots gives the total count for nodeCount.

class Solution {
public:
    int numTrees(int n) {
        std::vector<int> treeCounts(n + 1, 0);
        treeCounts[0] = 1;
        treeCounts[1] = 1;
        
        for (int nodeCount = 2; nodeCount <= n; ++nodeCount) {
            for (int root = 1; root <= nodeCount; ++root) {
                int leftSubtrees = treeCounts[root - 1];
                int rightSubtrees = treeCounts[nodeCount - root];
                treeCounts[nodeCount] += leftSubtrees * rightSubtrees;
            }
        }
        return treeCounts[n];
    }
};