343. Integer Break

Problem Link: LeetCode 343 - Integer Break
Given an integer n, break it into at least two positive integers, where the sum equals n. Return the maximum product possible from these integers.

Example:

• Input: 2
• Output: 1
• Explanation: 2 = 1 + 1, 1 × 1 = 1

Apprroach

This is a classic dynamic programming problem that can be solved using a bottom-up approach.

Step 1: Define the DP State
Let result[i] represent the maximum product obtainable by breaking the integer i. This definition guides the entire solution.

Step 2: Establish the Recurrence Relation
How do we compute the maximum product for a given i?
We iterate through possible first number j (from 1 to i-1), and consider two cases:

• j × (i - j): Simply multiplying j with the remaining value
• j × result[i - j]: Breaking (i - j) further into smaller parts

The recurrence becomes:
result[i] = max(result[i], max(j × (i - j), j × result[i - j]))

The first case handles splitting into exactly two numbers, while the second handles splitting into three or more numbers.

Step 3: Initialize the DP Array
For result[0] and result[1], there is no valid breaking that makes sense. We start from result[2] = 1, which is the base case for breaking 2 into 1 + 1.

Step 4: Determine the Iteration Order
Since result[i] depends on result[i - j] (smaller values), we iterate from smaller to larger values:

class Solution {
public:
    int integerBreak(int n) {
        vector<int> memo(n + 1, 0);
        memo[2] = 1;
        
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j <= i / 2; j++) {
                int option1 = j * (i - j);
                int option2 = j * memo[i - j];
                memo[i] = max(memo[i], max(option1, option2));
            }
        }
        return memo[n];
    }
};

We optimize by limiting j to i / 2 becuase the product becomes symmetric beyond that point.

96. Unique Binary Search Trees

Problem Link: LeetCode 96 - Unique Binary Search Trees
Given an integer n, count how many structurally unique binary search trees can be formed using nodes numbered from 1 to n.

Example:

• Input: 3
• Output: 5

Approach

Step 1: Define the DP State
Let count[i] represent the number of unique BSTs that can be formed using nodes 1 through i.

Step 2: Establish the Recurrence Relation
For n nodes, we can choose any node j (from 1 to n) as the root:

• Nodes 1 through j-1 go to the left subtree (j-1 nodes)
• Nodes j+1 through n go to the right subtree (n-j nodes)

The number of trees with root j equals count[j-1] × count[n-j].

The recurrence: count[i] += count[j-1] × count[i-j] for each j from 1 to i.

Step 3: Initialize the DP Array
We define count[0] = 1 because an empty tree is a valid BST, and it serves as the base for multiplication in the recurrence.

Step 4: Determine the Iteration Order
We iterate from smaller to larger i since each count[i] depends on previously computed smaller values:

class Solution {
public:
    int numTrees(int n) {
        vector<int> memo(n + 1, 0);
        memo[0] = 1;
        
        for (int i = 1; i <= n; i++) {
            for (int root = 1; root <= i; root++) {
                memo[i] += memo[root - 1] * memo[i - root];
            }
        }
        return memo[n];
    }
};

Analysis

Both problems demonstrate the_power of dynamic programming in counting and optimization scenarios:

The key insight for Integer Break is recognizing that beyond splitting into two numbers, we can recursive split the remaining value.
For Unique BSTs, the problem reduces to counting all possible root selections and combining left and right subtree configurations.