LeetCode 343: Integer Break

Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers. Return the maximum product you can get.

Dynamic Programmign Approach

The problem can be solved using dynamic programming. The key insight is that the maximum product for a number i depends on the maximum products of smaller numbers.

• State Definition: Let maxProductCache[i] represent the maximum product obtainable by breaking the integer i.

• State Transition: For each integer i from 2 to n, we consider all possible ways to split it into two parts, j and i-j. For each split, we have two choices for the second part:

  • Do not break i-j further, rseulting in a product of j * (i-j).
  • Break i-j further, resulting in a product of j * maxProductCache[i-j].

  The maximum product for i is the maximum value among all these possibliities for all valid j.

• Initialization: maxProductCache[0] and maxProductCache[1] are 0 because they cannot be broken down. maxProductCache[2] is 1 (1+1).

• Result: The answer is maxProductCache[n].

Code (Dynamic Programming)

#include <vector>
#include <algorithm>

class Solution {
public:
    int integerBreak(int num) {
        if (num <= 3) {
            return num - 1;
        }

        std::vector<int> maxProductCache(num + 1, 0);
        maxProductCache[2] = 1;

        for (int i = 3; i <= num; ++i) {
            for (int j = 1; j <= i / 2; ++j) {
                // Calculate product by not breaking (i-j) and by breaking (i-j)
                int productWithoutBreak = j * (i - j);
                int productWithBreak = j * maxProductCache[i - j];
                
                // Update the cache for the current number i
                maxProductCache[i] = std::max({maxProductCache[i], productWithoutBreak, productWithBreak});
            }
        }
        return maxProductCache[num];
    }
};

Mathematical Approach

A more efficient solution leverages mathematical properties. The maximum product is achieved by breaking the number into as many 3s as possible. If a remainder of 1 is left, it's better to take one of the 3s and combine it with the 1 to make a 4 (since 2*2 > 3*1).

Code (Mathematical)

#include <cmath>

class Solution {
public:
    int integerBreak(int num) {
        if (num <= 3) {
            return num - 1;
        }

        int quotient = num / 3;
        int remainder = num % 3;

        if (remainder == 0) {
            return std::pow(3, quotient);
        } else if (remainder == 1) {
            return std::pow(3, quotient - 1) * 4;
        } else { // remainder == 2
            return std::pow(3, quotient) * 2;
        }
    }
};

LeetCode 96: Unique Binary Search Trees

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

Dynamic Programming Approach

This problem is a classic example of computing Catalan numbers. The number of unique BSTs for n nodes can be derived from the number of trees for fewer nodes.

• State Definition: Let treeCountCache[i] represent the number of unique BSTs that can be formed with i nodes.
• State Transition: For each number i from 1 to n, consider each number j from 1 to i as the root of the tree. The number of nodes in the left subtree will be j-1, and the number of nodes in the right subtree will be i-j. The total number of trees with i nodes and j as the root is the product of the number of left subtrees and right subtrees: treeCountCache[j-1] * treeCountCache[i-j]. We sum this product for all possible roots j to get treeCountCache[i].
• Initialization: treeCountCache[0] is 1, representing the empty tree, which is a valid BST.
• Result: The answer is treeCountCache[n].

Code

#include <vector>

class Solution {
public:
    int numTrees(int numNodes) {
        std::vector<int> treeCountCache(numNodes + 1, 0);
        treeCountCache[0] = 1; // Base case: one empty tree

        for (int i = 1; i <= numNodes; ++i) {
            for (int j = 1; j <= i; ++j) {
                // Number of left subtrees * Number of right subtrees
                treeCountCache[i] += treeCountCache[j - 1] * treeCountCache[i - j];
            }
        }
        return treeCountCache[numNodes];
    }
};