### LeetCode 343: Integer Break **Problem Link:** LeetCode 343. Integer Break **Problem Description:** Given a positive integer `n`, partition it into `k` positive integers (k >= 2) such that the product of these integers is maximized. Return the maximum product achievable. **Approach:** For this problem, we need to partition an integer into smaller parts. When `n >= 2`, we can always split it into at least two smaller integers. These integers can either be further partitioned or left as is. Since the maximum product for any number depends on the maximum products of smaller numbers, dynamic programming is an appropriate solution. - Define `dp[i]`: The maximum product achievable for the integer `i` - Calculate `dp[i]`: `dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j))` This formula comes from considering two cases: either we continue partitioning the smaller integer or we don't. Since we don't know which partition yields the maximum product, we need to evaluate all possibilities and keep the maximum value. - Initialization: Since 0 and 1 cannot be partitioned, `dp[0] = dp[1] = 0`, and `dp[2] = 1` - Result: `dp[n]` **Code Implementation (Dynamic Programming):** cpp class Solution { public: int integerBreak(int n) { int dp[61] = {0}; // Using slightly larger array for safety dp[2] = 1; for (int i = 3; i <= n; i++) { for (int j = 1; j <= i / 2; j++) { // Only need to check up to i/2 to avoid redundant calculations int currentMax = max(j * (i - j), j * dp[i - j]); dp[i] = max(dp[i], currentMax); } } return dp[n]; } }; - Time Complexity: O(n²) - Space Complexity: O(n) Additionally, there's a mathematical approach that leverages inequalities and calculus to optimize both time and space complexity: **Code Implementation (Mathematical Approach):** cpp class Solution { public: int integerBreak(int n) { if (n <= 3) { return n - 1; } int quotient = n / 3; int remainder = n % 3; if (remainder == 0) { return pow(3, quotient); } else if (remainder == 1) { return pow(3, quotient - 1) * 4; } else { // remainder == 2 return pow(3, quotient) * 2; } } }; - Time Complexity: O(1) - Only involves basic arithmetic operations - Space Complexity: O(1) - Uses constant extra space for variables ### LeetCode 96: Unique Binary Search Trees **Problem Link:** LeetCode 96. Unique Binary Search Trees **Problem Description:** Given an integer `n`, determine the number of structurally unique BSTs that can be formed with `n` nodes where node values range from 1 to n. **Approach:** For `n` nodes, the number of unique BSTs with `i` as the root equals the product of the number of BSTs in its left and right subtrees. - Define `dp[i]`: The number of unique BSTs that can be formed with `i` nodes (values 1 to i) - Calculate `dp[i]`: `dp[i] += dp[j - 1] * dp[i - j]`, where `j` ranges from 1 to i Here, `j-1` represents the number of nodes in the left subtree, and `i-j` represents the number of nodes in the right subtree when `j` is the root. - Initialization: `dp[0] = 1` because an empty tree is considered a valid BST - Result: `dp[n]` **Code Implementation:** cpp class Solution { public: int numTrees(int n) { vector dp(n + 1, 0); dp[0] = 1; // Base case: empty tree for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { dp[i] += dp[j - 1] * dp[i - j]; } } return dp[n]; } }; - Time Complexity: O(n²) - Space Complexity: O(n)