Dynamic Programming Study Guide - Blind 75 LeetCode Problems
Table of Contents
- Introduction to Dynamic Programming
- Core Concepts and Prerequisites
- Problem-First Approach to DP
- The 11 DP Problems
- Common DP Patterns Summary
- Space Optimization Techniques
Introduction to Dynamic Programming
Dynamic Programming (DP) is an algorithmic technique that solves complex problems by breaking them down into simpler subproblems. It’s particularly useful when the same subproblems occur multiple times in a recursive solution.
Key Characteristics of DP Problems:
- Optimal Substructure: Optimal solution can be constructed from optimal solutions of subproblems
- Overlapping Subproblems: Same subproblems are solved multiple times
- Decision Making: At each step, we make a choice that affects future decisions
Core Concepts and Prerequisites
1. Recursion
Understanding recursive problem-solving is fundamental to DP. Every DP problem starts with a recursive solution.
2. Memoization (Top-Down DP)
- Store results of expensive function calls
- Return cached result when same inputs occur again
- Uses recursion with memory
3. Tabulation (Bottom-Up DP)
- Build solution iteratively from base cases
- Fill up a table/array in a bottom-up manner
- Usually more space-efficient
4. State Definition
- Identify what parameters uniquely define a subproblem
- These parameters become dimensions of your DP table
Problem-First Approach to DP
How to Identify DP Problems:
- Optimization: Find maximum/minimum value
- Counting: Count number of ways to do something
- Decision Making: Yes/No questions about possibility
- Choices: At each step, you have multiple choices
- Future depends on past: Current decision affects future options
Steps to Solve DP Problems:
- Identify the recursive structure
- Define the state(s)
- Write the recurrence relation
- Identify base cases
- Implement memoization (top-down)
- Convert to tabulation (bottom-up)
- Optimize space if possible
The 11 DP Problems
1. Climbing Stairs
🔗 LeetCode Link: Climbing Stairs - LeetCode #70
🤔 Think First (Active Retrieval)
Before reading the solution, spend 2-3 minutes thinking about this problem:
Quick Reflection Questions:
- If you’re standing at step n, what are the only two ways you could have arrived there?
- How might the number of ways to reach step n relate to the number of ways to reach previous steps?
- What would be the base cases for very small values (like n=1 or n=2)?
Take a moment to think through these questions before continuing…
💡 Discovery Process (Guided Learning)
Step 1: Pattern Recognition
Guided Question: Look at small examples: n=1 (1 way), n=2 (2 ways), n=3 (?). Can you find a pattern by thinking about how to reach step 3?
💭 Think about it, then click to reveal
To reach step 3, you can either: - Come from step 2 by taking 1 step - Come from step 1 by taking 2 steps Since there are 2 ways to reach step 2 and 1 way to reach step 1, there are 2 + 1 = 3 ways to reach step 3. This reveals the Fibonacci pattern: `ways(n) = ways(n-1) + ways(n-2)`Step 2: Recurrence Relation Discovery
Guided Question: Why does this recurrence relation make sense? What choice are you making at each step?
💭 Think about it, then click to reveal
At each step, you have exactly two choices: - Take a 1-step (which means you need to count all ways to reach the previous step) - Take a 2-step (which means you need to count all ways to reach the step before that) The recurrence captures this decision-making process. The total ways is the sum of both choices.Step 3: Implementation Strategy
Guided Question: Given this recurrence relation, what’s the most efficient way to compute the answer? Do you need to store all previous values?
💭 Think about it, then click to reveal
Since each value only depends on the two previous values, you only need to store the last two results as you iterate. This gives you O(1) space complexity instead of O(n). You can also use memoization (top-down) or tabulation (bottom-up) depending on your preference.🎯 Practice & Self-Assessment
Implementation Challenge
Try implementing the optimal solution from memory:
Step-by-step checklist:
- Handle base cases (n ≤ 1)
- Initialize first two values (ways to reach step 0 and 1)
- Use either iteration with two variables or DP array
- Apply recurrence: current = prev1 + prev2
- Return the result for step n
Reflection Questions
After solving, think about:
- Understanding Check: Can you explain why this problem follows the Fibonacci sequence?
- Complexity Analysis: What’s the time and space complexity of your solution?
- Trade-offs: When would you choose memoization vs tabulation vs space-optimized iteration?
- Pattern Recognition: What other problems might use this same “sum of previous states” pattern?
Confidence Rating
Rate your confidence (1-5) on:
- Understanding the problem: ___/5
- Implementing brute force: ___/5
- Implementing optimal solution: ___/5
- Explaining the approach: ___/5
Next Steps
- If confidence is 3+ on all: Move to next problem
- If confidence is <3: Review the guided discovery section again
- Consider trying variations like “Climbing Stairs with k steps” or “Min Cost Climbing Stairs”
Problem Statement: You’re climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Example:
- Input: n = 3
- Output: 3 (1+1+1, 1+2, 2+1)
Knowledge Prerequisites:
- Basic recursion
- Understanding of Fibonacci sequence
- Memoization concepts
First Principles: To reach step n, you can come from:
- Step (n-1) by taking 1 step
- Step (n-2) by taking 2 steps
This gives us: ways(n) = ways(n-1) + ways(n-2)
Problem-First Approach:
- Identify pattern: At each step, we have 2 choices (1 or 2 steps)
- State definition:
dp[i]= number of ways to reach step i - Recurrence:
dp[i] = dp[i-1] + dp[i-2] - Base cases:
dp[0] = 1,dp[1] = 1
Solutions:
// Approach 1: Recursive with Memoization (Top-Down)
class ClimbingStairs {
public int climbStairs(int n) {
int[] memo = new int[n + 1];
return helper(n, memo);
}
private int helper(int n, int[] memo) {
// Base cases
if (n <= 1) return 1;
// Check memo
if (memo[n] != 0) return memo[n];
// Recurrence relation
memo[n] = helper(n - 1, memo) + helper(n - 2, memo);
return memo[n];
}
}
// Approach 2: Iterative Bottom-Up (Tabulation)
class ClimbingStairs {
public int climbStairs(int n) {
if (n <= 1) return 1;
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
// Approach 3: Space Optimized
class ClimbingStairs {
public int climbStairs(int n) {
if (n <= 1) return 1;
int prev2 = 1, prev1 = 1;
for (int i = 2; i <= n; i++) {
int current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
}
```python
# Approach 1: Recursive with Memoization (Top-Down)
class ClimbingStairs:
def climbStairs(self, n: int) -> int:
memo = {}
return self.helper(n, memo)
def helper(self, n: int, memo: dict) -> int:
# Base cases
if n <= 1:
return 1
# Check memo
if n in memo:
return memo[n]
# Recurrence relation
memo[n] = self.helper(n - 1, memo) + self.helper(n - 2, memo)
return memo[n]
# Approach 2: Iterative Bottom-Up (Tabulation)
class ClimbingStairs:
def climbStairs(self, n: int) -> int:
if n <= 1:
return 1
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# Approach 3: Space Optimized
class ClimbingStairs:
def climbStairs(self, n: int) -> int:
if n <= 1:
return 1
prev2, prev1 = 1, 1
for i in range(2, n + 1):
current = prev1 + prev2
prev2 = prev1
prev1 = current
return prev1
```
```javascript
// Approach 1: Recursive with Memoization (Top-Down)
class ClimbingStairs {
climbStairs(n) {
const memo = new Map();
return this.helper(n, memo);
}
helper(n, memo) {
// Base cases
if (n <= 1) return 1;
// Check memo
if (memo.has(n)) return memo.get(n);
// Recurrence relation
const result = this.helper(n - 1, memo) + this.helper(n - 2, memo);
memo.set(n, result);
return result;
}
}
// Approach 2: Iterative Bottom-Up (Tabulation)
class ClimbingStairs {
climbStairs(n) {
if (n <= 1) return 1;
const dp = new Array(n + 1);
dp[0] = 1;
dp[1] = 1;
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
// Approach 3: Space Optimized
class ClimbingStairs {
climbStairs(n) {
if (n <= 1) return 1;
let prev2 = 1, prev1 = 1;
for (let i = 2; i <= n; i++) {
const current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
}
```
Complexity Analysis:
- Memoization: Time O(n), Space O(n)
- Tabulation: Time O(n), Space O(n)
- Space Optimized: Time O(n), Space O(1)
Key Insights & Patterns:
- This is the classic Fibonacci pattern
- Applicable to problems where answer depends on previous few states
- Foundation for more complex step-based problems
State Transition Explanation:
dp[i] = dp[i-1] + dp[i-2]
The number of ways to reach step i equals the sum of ways to reach the two previous steps.
2. Coin Change
🔗 LeetCode Link: Coin Change - LeetCode #322
🤔 Think First (Active Retrieval)
Before reading the solution, spend 2-3 minutes thinking about this problem:
Quick Reflection Questions:
- Why might a greedy approach (always choosing the largest coin) fail for this problem?
- If you want to make amount X, what coin choices give you subproblems you might have already solved?
- What should you return if it’s impossible to make the exact amount?
Take a moment to think through these questions before continuing…
💡 Discovery Process (Guided Learning)
Step 1: Understanding the Optimization Problem
Guided Question: What makes this different from simply counting ways? Why can’t you just use any coin combination?
💭 Think about it, then click to reveal
This is an optimization problem - you want the **minimum** number of coins, not just any valid combination. This means at each step, you need to consider all possible coin choices and pick the one that leads to the optimal solution. The key insight: for amount X, you need to try using each coin denomination and see which choice leads to the minimum total coins.Step 2: Recurrence Relation Discovery
Guided Question: If you use a coin of value C to make amount X, what’s the remaining subproblem? How does this help you build a recurrence?
💭 Think about it, then click to reveal
If you use coin C for amount X, you need the minimum coins for amount (X - C), plus 1 for the coin you just used. Recurrence: `dp[amount] = min(dp[amount - coin] + 1)` for all valid coins The "min" operation is crucial - you're exploring all coin choices and taking the best one.Step 3: Handling Edge Cases and Implementation
Guided Question: What should your base case be? How do you handle impossible amounts? How do you ensure you don’t use a coin larger than the current amount?
💭 Think about it, then click to reveal
- Base case: `dp[0] = 0` (zero coins needed for amount 0) - For impossible amounts: Initialize with a value larger than any possible answer (like amount + 1) - Constraint check: Only use coin if `coin <= current_amount` - Final check: If result > amount, return -1 (impossible) This is an "unbounded knapsack" problem - you can use each coin multiple times.🎯 Practice & Self-Assessment
Implementation Challenge
Try implementing the optimal solution from memory:
Step-by-step checklist:
- Initialize DP array with impossible values (amount + 1)
- Set base case: dp[0] = 0
- For each amount from 1 to target, try all coins
- Only use coin if coin <= current amount
- Take minimum: dp[amount] = min(dp[amount], dp[amount - coin] + 1)
- Return dp[amount] > amount ? -1 : dp[amount]
Reflection Questions
After solving, think about:
- Understanding Check: Why does greedy approach fail? Can you give a counter-example?
- Complexity Analysis: What’s the time complexity in terms of amount and number of coins?
- Trade-offs: When would you use top-down vs bottom-up approach?
- Pattern Recognition: How is this similar to unbounded knapsack problems?
Confidence Rating
Rate your confidence (1-5) on:
- Understanding the problem: ___/5
- Implementing brute force: ___/5
- Implementing optimal solution: ___/5
- Explaining the approach: ___/5
Next Steps
- If confidence is 3+ on all: Move to next problem
- If confidence is <3: Review the guided discovery section again
- Consider trying “Coin Change 2” (counting combinations) to deepen understanding
Problem Statement: Given coins of certain denominations and a total amount, find the minimum number of coins needed to make up that amount. Return -1 if impossible.
Example:
- Input: coins = [1,3,4], amount = 6
- Output: 2 (3+3)
Knowledge Prerequisites:
- Understanding of optimization problems
- Greedy vs optimal approach awareness
- Infinite supply concept
First Principles:
For each amount, try using each coin and take the minimum:
dp[amount] = min(dp[amount - coin] + 1) for all valid coins
Problem-First Approach:
- Identify pattern: Optimization problem with choices
- State definition:
dp[i]= minimum coins needed for amount i - Recurrence:
dp[i] = min(dp[i], dp[i - coin] + 1)for each coin - Base case:
dp[0] = 0
Solutions:
// Approach 1: Recursive with Memoization (Top-Down)
class CoinChange {
public int coinChange(int[] coins, int amount) {
int[] memo = new int[amount + 1];
Arrays.fill(memo, -1);
int result = helper(coins, amount, memo);
return result == Integer.MAX_VALUE ? -1 : result;
}
private int helper(int[] coins, int amount, int[] memo) {
// Base cases
if (amount == 0) return 0;
if (amount < 0) return Integer.MAX_VALUE;
// Check memo
if (memo[amount] != -1) return memo[amount];
int minCoins = Integer.MAX_VALUE;
// Try each coin
for (int coin : coins) {
int subResult = helper(coins, amount - coin, memo);
if (subResult != Integer.MAX_VALUE) {
minCoins = Math.min(minCoins, subResult + 1);
}
}
memo[amount] = minCoins;
return minCoins;
}
}
// Approach 2: Iterative Bottom-Up (Tabulation)
class CoinChange {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1); // Initialize with impossible value
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int coin : coins) {
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
```python
# Approach 1: Recursive with Memoization (Top-Down)
class CoinChange:
def coinChange(self, coins, amount):
memo = {}
def helper(amount):
# Base cases
if amount == 0:
return 0
if amount < 0:
return float('inf')
# Check memo
if amount in memo:
return memo[amount]
min_coins = float('inf')
# Try each coin
for coin in coins:
sub_result = helper(amount - coin)
if sub_result != float('inf'):
min_coins = min(min_coins, sub_result + 1)
memo[amount] = min_coins
return min_coins
result = helper(amount)
return result if result != float('inf') else -1
# Approach 2: Iterative Bottom-Up (Tabulation)
class CoinChange:
def coinChange(self, coins, amount):
dp = [amount + 1] * (amount + 1) # Initialize with impossible value
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] <= amount else -1
```
```javascript
// Approach 1: Recursive with Memoization (Top-Down)
class CoinChange {
coinChange(coins, amount) {
const memo = new Map();
const helper = (amount) => {
// Base cases
if (amount === 0) return 0;
if (amount < 0) return Infinity;
// Check memo
if (memo.has(amount)) return memo.get(amount);
let minCoins = Infinity;
// Try each coin
for (const coin of coins) {
const subResult = helper(amount - coin);
if (subResult !== Infinity) {
minCoins = Math.min(minCoins, subResult + 1);
}
}
memo.set(amount, minCoins);
return minCoins;
};
const result = helper(amount);
return result === Infinity ? -1 : result;
}
}
// Approach 2: Iterative Bottom-Up (Tabulation)
class CoinChange {
coinChange(coins, amount) {
const dp = new Array(amount + 1).fill(amount + 1); // Initialize with impossible value
dp[0] = 0;
for (let i = 1; i <= amount; i++) {
for (const coin of coins) {
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
```
Complexity Analysis:
- Time: O(amount × coins.length)
- Space: O(amount)
Key Insights & Patterns:
- Classic “unbounded knapsack” variant
- Greedy approach doesn’t always work
- Pattern applicable to resource optimization problems
State Transition Explanation:
dp[i] = min(dp[i], dp[i - coin] + 1) for each coin where coin <= i
For amount i, try using each coin and take the minimum cost.
3. Longest Increasing Subsequence
🔗 LeetCode Link: Longest Increasing Subsequence - LeetCode #300
🤔 Think First (Active Retrieval)
Before reading the solution, spend 2-3 minutes thinking about this problem:
Quick Reflection Questions:
- What’s the difference between a subsequence and a subarray? Why does this matter for the problem?
- For each element in the array, what decision do you need to make regarding the longest increasing subsequence?
- If you know the LIS ending at each previous position, how can you determine the LIS ending at the current position?
Take a moment to think through these questions before continuing…
💡 Discovery Process (Guided Learning)
Step 1: Understanding Subsequences vs Subarrays
Guided Question: Given array [10,9,2,5,3,7,101,18], what’s a valid increasing subsequence? Does it need to be contiguous?
💭 Think about it, then click to reveal
A subsequence maintains relative order but doesn't need to be contiguous. For example: - [2,5,7,101] is valid (indices 2,3,5,6) - [10,101] is valid (indices 0,6) - [9,2,5] is invalid (not increasing) This means for each element, you can either include it in your LIS or skip it, but you must maintain the relative order from the original array.Step 2: State Definition and Recurrence
Guided Question: If dp[i] represents the length of LIS ending at index i, how do you compute dp[i] using previous values?
💭 Think about it, then click to reveal
For each position i, you look at all previous positions j where nums[j] < nums[i]. You can extend any LIS ending at position j by including nums[i]. Recurrence: `dp[i] = max(dp[j] + 1)` for all j < i where nums[j] < nums[i] Base case: `dp[i] = 1` (each element forms a subsequence of length 1 by itself) The final answer is `max(dp[i])` across all positions.Step 3: Optimization Insight
Guided Question: The basic DP solution is O(n²). Can you think of a way to use binary search to improve this? What would you need to maintain?
💭 Think about it, then click to reveal
Key insight: Maintain an array where `tails[i]` = smallest ending element of all increasing subsequences of length i+1. For each new element: - If it's larger than all elements in tails, append it (extend longest sequence) - Otherwise, use binary search to find the position where it should replace an existing element This works because replacing a larger element with a smaller one gives us better potential for future extensions, while maintaining the same length. Time complexity: O(n log n)🎯 Practice & Self-Assessment
Implementation Challenge
Try implementing both the O(n²) and O(n log n) solutions:
Step-by-step checklist (O(n²) DP):
- Initialize dp array where dp[i] = 1 for all i
- For each position i, check all previous positions j
- If nums[j] < nums[i], update dp[i] = max(dp[i], dp[j] + 1)
- Return the maximum value in dp array
Step-by-step checklist (O(n log n) Binary Search):
- Maintain tails array for smallest endings
- For each element, use binary search to find insertion position
- Either append (if larger than all) or replace element at found position
- Return length of tails array
Reflection Questions
After solving, think about:
- Understanding Check: Can you explain why the tails array optimization works?
- Complexity Analysis: Why is the binary search approach faster? When would you use each?
- Trade-offs: What are the space requirements for each approach?
- Pattern Recognition: What other subsequence problems use similar techniques?
Confidence Rating
Rate your confidence (1-5) on:
- Understanding the problem: ___/5
- Implementing brute force: ___/5
- Implementing optimal solution: ___/5
- Explaining the approach: ___/5
Next Steps
- If confidence is 3+ on all: Move to next problem
- If confidence is <3: Review the guided discovery section again
- Consider trying “Russian Doll Envelopes” or “Number of LIS” for advanced practice
Problem Statement: Given an integer array, return the length of the longest strictly increasing subsequence.
Example:
- Input: [10,9,2,5,3,7,101,18]
- Output: 4 ([2,3,7,101])
Knowledge Prerequisites:
- Subsequence vs subarray understanding
- Binary search (for optimized solution)
- Patience sorting concept
First Principles: For each element, we can either:
- Start a new subsequence
- Extend an existing subsequence if current element is larger
Problem-First Approach:
- Identify pattern: Subsequence optimization problem
- State definition:
dp[i]= length of LIS ending at index i - Recurrence:
dp[i] = max(dp[j] + 1)for all j < i where arr[j] < arr[i] - Base case:
dp[i] = 1for all i
Solutions:
// Approach 1: DP Solution O(n²)
class LongestIncreasingSubsequence {
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) return 0;
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int maxLength = 1;
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLength = Math.max(maxLength, dp[i]);
}
return maxLength;
}
}
// Approach 2: Binary Search + DP O(n log n)
class LongestIncreasingSubsequence {
public int lengthOfLIS(int[] nums) {
List<Integer> tails = new ArrayList<>();
for (int num : nums) {
int pos = binarySearch(tails, num);
if (pos == tails.size()) {
tails.add(num);
} else {
tails.set(pos, num);
}
}
return tails.size();
}
private int binarySearch(List<Integer> tails, int target) {
int left = 0, right = tails.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (tails.get(mid) < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}
```python
# Approach 1: DP Solution O(n²)
class LongestIncreasingSubsequence:
def lengthOfLIS(self, nums):
if not nums:
return 0
dp = [1] * len(nums)
max_length = 1
for i in range(1, len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
max_length = max(max_length, dp[i])
return max_length
# Approach 2: Binary Search + DP O(n log n)
import bisect
class LongestIncreasingSubsequence:
def lengthOfLIS(self, nums):
tails = []
for num in nums:
pos = bisect.bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)
```
```javascript
// Approach 1: DP Solution O(n²)
class LongestIncreasingSubsequence {
lengthOfLIS(nums) {
if (nums.length === 0) return 0;
const dp = new Array(nums.length).fill(1);
let maxLength = 1;
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLength = Math.max(maxLength, dp[i]);
}
return maxLength;
}
}
// Approach 2: Binary Search + DP O(n log n)
class LongestIncreasingSubsequence {
lengthOfLIS(nums) {
const tails = [];
for (const num of nums) {
const pos = this.binarySearch(tails, num);
if (pos === tails.length) {
tails.push(num);
} else {
tails[pos] = num;
}
}
return tails.length;
}
binarySearch(tails, target) {
let left = 0, right = tails.length;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (tails[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}
```
Complexity Analysis:
- DP Approach: Time O(n²), Space O(n)
- Binary Search: Time O(n log n), Space O(n)
Key Insights & Patterns:
- Classic subsequence optimization
- Binary search optimization technique
- Pattern for "longest/shortest subsequence" problems
State Transition Explanation:
-
---
### 4. Longest Common Subsequence
**🔗 LeetCode Link:** [Longest Common Subsequence - LeetCode #1143](https://leetcode.com/problems/longest-common-subsequence/)
### 🤔 Think First (Active Retrieval)
Before reading the solution, spend 2-3 minutes thinking about this problem:
**Quick Reflection Questions:**
1. When comparing two strings character by character, what are the possible decisions you can make at each step?
2. If characters at current positions match, how does this affect the LCS? If they don't match?
3. Why might this require a 2D DP table instead of a 1D array?
*Take a moment to think through these questions before continuing...*
### 💡 Discovery Process (Guided Learning)
#### Step 1: Understanding the Decision Space
> **Guided Question:** At each position (i,j) in the two strings, what are all the possible choices you have for building the LCS?
- 2D DP: Time O(m×n), Space O(m×n)
- Space Optimized: Time O(m×n), Space O(min(m,n))
- Time: O(n² × m) where n = string length, m = average word length
- Space: O(n + W) where W = total characters in dictionary
- Optimized: O(n × maxWordLength × m)
- Backtracking: O(2^target) in worst case
- DP Counting: Time O(target × nums.length), Space O(target)
- Time: O(n)
- Space: O(n) for DP array, O(1) for optimized version
- Time: O(n)
- Space: O(1)
- Time: O(n)
- Space: O(n) for DP, O(1) for optimized
- Similar to Fibonacci but with validity constraints
- Pattern for string parsing with multiple interpretations
- Handling edge cases with invalid characters
- 2D DP: Time O(m×n), Space O(m×n)
- 1D DP: Time O(m×n), Space O(n)
- Mathematical: Time O(min(m,n)), Space O(1)
- DP: Time O(n²), Space O(n)
- Greedy: Time O(n), Space O(1)
- Backward: Time O(n), Space O(1)
💭 Think about it, then click to reveal
When comparing text1[i] and text2[j], you have three choices: 1. If characters match: Include this character in LCS (move diagonally) 2. Skip current character in text1 (move down in the table) 3. Skip current character in text2 (move right in the table) The key insight: You're trying all possible ways to align the two strings to find the longest common subsequence.💭 Think about it, then click to reveal
`dp[i][j]` = length of LCS between first i characters of text1 and first j characters of text2. You need 2D because the state depends on positions in BOTH strings. Each cell represents the optimal solution for a specific prefix combination. Recurrence: - If text1[i-1] == text2[j-1]: `dp[i][j] = dp[i-1][j-1] + 1` - Else: `dp[i][j] = max(dp[i-1][j], dp[i][j-1])`💭 Think about it, then click to reveal
**When characters match**: You've found a character that contributes to the LCS! Include it and continue with the remaining substrings (dp[i-1][j-1] + 1). **When characters don't match**: One of the current characters won't be in the optimal LCS. Try skipping each character and take the better option: - Skip from text1: dp[i-1][j] - Skip from text2: dp[i][j-1] - Take the maximum This covers all possible alignments systematically.// Approach 1: 2D DP
class LongestCommonSubsequence {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
}
// Approach 2: Space Optimized (1D DP)
class LongestCommonSubsequence {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
// Use shorter string for space optimization
if (m < n) {
return longestCommonSubsequence(text2, text1);
}
int[] dp = new int[n + 1];
for (int i = 1; i <= m; i++) {
int prev = 0;
for (int j = 1; j <= n; j++) {
int temp = dp[j];
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[j] = prev + 1;
} else {
dp[j] = Math.max(dp[j], dp[j - 1]);
}
prev = temp;
}
}
return dp[n];
}
}
// Approach 3: Recursive with Memoization
class LongestCommonSubsequence {
public int longestCommonSubsequence(String text1, String text2) {
int[][] memo = new int[text1.length()][text2.length()];
for (int[] row : memo) {
Arrays.fill(row, -1);
}
return helper(text1, text2, 0, 0, memo);
}
private int helper(String text1, String text2, int i, int j, int[][] memo) {
if (i == text1.length() || j == text2.length()) {
return 0;
}
if (memo[i][j] != -1) {
return memo[i][j];
}
if (text1.charAt(i) == text2.charAt(j)) {
memo[i][j] = 1 + helper(text1, text2, i + 1, j + 1, memo);
} else {
memo[i][j] = Math.max(
helper(text1, text2, i + 1, j, memo),
helper(text1, text2, i, j + 1, memo)
);
}
return memo[i][j];
}
}
```python
# Approach 1: 2D DP
class LongestCommonSubsequence:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
# Approach 2: Space Optimized (1D DP)
class LongestCommonSubsequence:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
# Use shorter string for space optimization
if m < n:
return self.longestCommonSubsequence(text2, text1)
dp = [0] * (n + 1)
for i in range(1, m + 1):
prev = 0
for j in range(1, n + 1):
temp = dp[j]
if text1[i - 1] == text2[j - 1]:
dp[j] = prev + 1
else:
dp[j] = max(dp[j], dp[j - 1])
prev = temp
return dp[n]
# Approach 3: Recursive with Memoization
class LongestCommonSubsequence:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
memo = {}
def helper(i, j):
if i == len(text1) or j == len(text2):
return 0
if (i, j) in memo:
return memo[(i, j)]
if text1[i] == text2[j]:
memo[(i, j)] = 1 + helper(i + 1, j + 1)
else:
memo[(i, j)] = max(helper(i + 1, j), helper(i, j + 1))
return memo[(i, j)]
return helper(0, 0)
```
```javascript
// Approach 1: 2D DP
class LongestCommonSubsequence {
longestCommonSubsequence(text1, text2) {
const m = text1.length, n = text2.length;
const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (text1[i - 1] === text2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
}
// Approach 2: Space Optimized (1D DP)
class LongestCommonSubsequence {
longestCommonSubsequence(text1, text2) {
let m = text1.length, n = text2.length;
// Use shorter string for space optimization
if (m < n) {
return this.longestCommonSubsequence(text2, text1);
}
const dp = new Array(n + 1).fill(0);
for (let i = 1; i <= m; i++) {
let prev = 0;
for (let j = 1; j <= n; j++) {
const temp = dp[j];
if (text1[i - 1] === text2[j - 1]) {
dp[j] = prev + 1;
} else {
dp[j] = Math.max(dp[j], dp[j - 1]);
}
prev = temp;
}
}
return dp[n];
}
}
// Approach 3: Recursive with Memoization
class LongestCommonSubsequence {
longestCommonSubsequence(text1, text2) {
const memo = new Map();
const helper = (i, j) => {
if (i === text1.length || j === text2.length) {
return 0;
}
const key = `${i},${j}`;
if (memo.has(key)) {
return memo.get(key);
}
let result;
if (text1[i] === text2[j]) {
result = 1 + helper(i + 1, j + 1);
} else {
result = Math.max(helper(i + 1, j), helper(i, j + 1));
}
memo.set(key, result);
return result;
};
return helper(0, 0);
}
}
```
Complexity Analysis:
💭 Think about it, then click to reveal
You need to try all possible prefix-suffix splits: - For each position i in the string, check if prefix[0...i] is a valid word - If it is, recursively check if the remaining suffix can also be broken This creates a tree of possibilities where each node represents a potential word boundary. The key insight: If you can break string[0...j] AND string[j+1...i] is a valid word, then you can break string[0...i].💭 Think about it, then click to reveal
`dp[i]` = true if string[0...i-1] can be segmented into dictionary words. This is a **boolean DP** problem - you're checking possibility, not optimizing a value. Recurrence: `dp[i] = true` if there exists any j where: - `dp[j] = true` (prefix can be broken) - `string[j...i-1]` is in dictionary (current segment is valid) Base case: `dp[0] = true` (empty string can always be "broken")💭 Think about it, then click to reveal
**Dictionary Optimization**: Use HashSet for O(1) lookup instead of List with O(n) search. **Length Optimization**: Instead of checking all possible j values, only check j values within the maximum word length in the dictionary. This can significantly reduce the search space. **Early Termination**: Once you find one valid split for dp[i], you can break early since you only need to know if it's possible.// Approach 1: Bottom-Up DP
class WordBreak {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> wordSet = new HashSet<>(wordDict);
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordSet.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}
// Approach 2: Top-Down with Memoization
class WordBreak {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> wordSet = new HashSet<>(wordDict);
Boolean[] memo = new Boolean[s.length()];
return helper(s, 0, wordSet, memo);
}
private boolean helper(String s, int start, Set<String> wordSet, Boolean[] memo) {
if (start == s.length()) {
return true;
}
if (memo[start] != null) {
return memo[start];
}
for (int end = start + 1; end <= s.length(); end++) {
String prefix = s.substring(start, end);
if (wordSet.contains(prefix) && helper(s, end, wordSet, memo)) {
memo[start] = true;
return true;
}
}
memo[start] = false;
return false;
}
}
// Approach 3: Optimized with Max Word Length
class WordBreak {
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> wordSet = new HashSet<>(wordDict);
int maxLen = 0;
for (String word : wordDict) {
maxLen = Math.max(maxLen, word.length());
}
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = Math.max(0, i - maxLen); j < i; j++) {
if (dp[j] && wordSet.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}
}
```python
# Approach 1: Bottom-Up DP
class WordBreak:
def wordBreak(self, s: str, wordDict: list) -> bool:
word_set = set(wordDict)
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return dp[len(s)]
# Approach 2: Top-Down with Memoization
class WordBreak:
def wordBreak(self, s: str, wordDict: list) -> bool:
word_set = set(wordDict)
memo = {}
def helper(start):
if start == len(s):
return True
if start in memo:
return memo[start]
for end in range(start + 1, len(s) + 1):
prefix = s[start:end]
if prefix in word_set and helper(end):
memo[start] = True
return True
memo[start] = False
return False
return helper(0)
# Approach 3: Optimized with Max Word Length
class WordBreak:
def wordBreak(self, s: str, wordDict: list) -> bool:
word_set = set(wordDict)
max_len = max(len(word) for word in wordDict) if wordDict else 0
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(1, len(s) + 1):
for j in range(max(0, i - max_len), i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return dp[len(s)]
```
```javascript
// Approach 1: Bottom-Up DP
class WordBreak {
wordBreak(s, wordDict) {
const wordSet = new Set(wordDict);
const dp = new Array(s.length + 1).fill(false);
dp[0] = true;
for (let i = 1; i <= s.length; i++) {
for (let j = 0; j < i; j++) {
if (dp[j] && wordSet.has(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length];
}
}
// Approach 2: Top-Down with Memoization
class WordBreak {
wordBreak(s, wordDict) {
const wordSet = new Set(wordDict);
const memo = new Map();
const helper = (start) => {
if (start === s.length) {
return true;
}
if (memo.has(start)) {
return memo.get(start);
}
for (let end = start + 1; end <= s.length; end++) {
const prefix = s.substring(start, end);
if (wordSet.has(prefix) && helper(end)) {
memo.set(start, true);
return true;
}
}
memo.set(start, false);
return false;
};
return helper(0);
}
}
// Approach 3: Optimized with Max Word Length
class WordBreak {
wordBreak(s, wordDict) {
const wordSet = new Set(wordDict);
const maxLen = Math.max(...wordDict.map(word => word.length));
const dp = new Array(s.length + 1).fill(false);
dp[0] = true;
for (let i = 1; i <= s.length; i++) {
for (let j = Math.max(0, i - maxLen); j < i; j++) {
if (dp[j] && wordSet.has(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length];
}
}
```
Complexity Analysis:
💭 Think about it, then click to reveal
There are actually multiple variants: - **Combination Sum I**: List all unique combinations that sum to target (Backtracking) - **Combination Sum IV**: Count number of combinations that sum to target (DP) For **listing combinations**: Use backtracking to explore all possibilities For **counting combinations**: Use DP to avoid recomputing the same subproblems The key insight: DP is ideal when you only need the count, not the actual combinations.💭 Think about it, then click to reveal
This is an **unbounded knapsack** problem: - "Unbounded" = you can use each item (number) unlimited times - "Knapsack" = you're trying to achieve a target sum (capacity) Recurrence for counting: `dp[target] = sum(dp[target - num])` for all valid nums This is similar to Coin Change, but instead of minimizing coins, you're counting ways to make the target.💭 Think about it, then click to reveal
**Order matters** in Combination Sum IV: [1,2] and [2,1] are counted as different combinations. This means for each target sum, you try adding each number and count all the ways to make the remaining sum. **Implementation difference**: - Iterate through target sums (outer loop) - For each target, try all numbers (inner loop) - This ensures all orderings are considered If order didn't matter, you'd iterate through numbers first to avoid duplicates.// Approach 1: Backtracking (Standard Solution)
class CombinationSum {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> current = new ArrayList<>();
backtrack(candidates, target, 0, current, result);
return result;
}
private void backtrack(int[] candidates, int target, int start,
List<Integer> current, List<List<Integer>> result) {
if (target == 0) {
result.add(new ArrayList<>(current));
return;
}
for (int i = start; i < candidates.length; i++) {
if (candidates[i] <= target) {
current.add(candidates[i]);
backtrack(candidates, target - candidates[i], i, current, result);
current.remove(current.size() - 1);
}
}
}
}
// Approach 2: DP for Counting Combinations
class CombinationSum {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 1; i <= target; i++) {
for (int num : nums) {
if (num <= i) {
dp[i] += dp[i - num];
}
}
}
return dp[target];
}
}
// Approach 3: DP for Checking Possibility
class CombinationSum {
public boolean canPartition(int[] nums, int target) {
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int num : nums) {
for (int i = target; i >= num; i--) {
dp[i] = dp[i] || dp[i - num];
}
}
return dp[target];
}
}
```python
# Approach 1: Backtracking (Standard Solution)
class CombinationSum:
def combinationSum(self, candidates, target):
result = []
def backtrack(remaining, current, start):
if remaining == 0:
result.append(current[:]) # Add copy of current
return
for i in range(start, len(candidates)):
if candidates[i] <= remaining:
current.append(candidates[i])
backtrack(remaining - candidates[i], current, i)
current.pop()
backtrack(target, [], 0)
return result
# Approach 2: DP for Counting Combinations
class CombinationSum:
def combinationSum4(self, nums, target):
dp = [0] * (target + 1)
dp[0] = 1
for i in range(1, target + 1):
for num in nums:
if num <= i:
dp[i] += dp[i - num]
return dp[target]
# Approach 3: DP for Checking Possibility
class CombinationSum:
def canPartition(self, nums, target):
dp = [False] * (target + 1)
dp[0] = True
for num in nums:
for i in range(target, num - 1, -1):
dp[i] = dp[i] or dp[i - num]
return dp[target]
```
```javascript
// Approach 1: Backtracking (Standard Solution)
class CombinationSum {
combinationSum(candidates, target) {
const result = [];
const backtrack = (remaining, current, start) => {
if (remaining === 0) {
result.push([...current]); // Add copy of current
return;
}
for (let i = start; i < candidates.length; i++) {
if (candidates[i] <= remaining) {
current.push(candidates[i]);
backtrack(remaining - candidates[i], current, i);
current.pop();
}
}
};
backtrack(target, [], 0);
return result;
}
}
// Approach 2: DP for Counting Combinations
class CombinationSum {
combinationSum4(nums, target) {
const dp = new Array(target + 1).fill(0);
dp[0] = 1;
for (let i = 1; i <= target; i++) {
for (const num of nums) {
if (num <= i) {
dp[i] += dp[i - num];
}
}
}
return dp[target];
}
}
// Approach 3: DP for Checking Possibility
class CombinationSum {
canPartition(nums, target) {
const dp = new Array(target + 1).fill(false);
dp[0] = true;
for (const num of nums) {
for (let i = target; i >= num; i--) {
dp[i] = dp[i] || dp[i - num];
}
}
return dp[target];
}
}
```
Complexity Analysis:
💭 Think about it, then click to reveal
The adjacent constraint means that if you rob house i, you cannot rob house i-1 or i+1. This creates a fundamental choice at each house: - **Choice 1**: Rob this house (and thus skip the previous house) - **Choice 2**: Skip this house (and keep whatever optimal solution you had up to the previous house) A greedy approach fails because a high-value house might be surrounded by other high-value houses, making the local optimal choice globally suboptimal. This constraint pattern appears in many DP problems - decisions have consequences that ripple through future choices.💭 Think about it, then click to reveal
For house i, you have exactly two options: **Option 1 - Rob house i**: - You get nums[i] money from this house - But you cannot rob house i-1, so you get the best solution from houses 0 to i-2 - Total: `nums[i] + dp[i-2]` **Option 2 - Skip house i**: - You get 0 money from this house - But you keep the best solution from houses 0 to i-1 - Total: `dp[i-1]` Recurrence: `dp[i] = max(nums[i] + dp[i-2], dp[i-1])` This is similar to Fibonacci, but with a max operation and values from the array!💭 Think about it, then click to reveal
Since dp[i] only depends on dp[i-1] and dp[i-2], you only need to track the last two values as you iterate forward. **Space optimization pattern**: - `prev2` = dp[i-2] (best solution excluding previous house) - `prev1` = dp[i-1] (best solution including previous house) - `current` = max(prev1, prev2 + nums[i]) This reduces space complexity from O(n) to O(1) while maintaining the same logic. This optimization pattern appears frequently in linear DP problems.// Approach 1: Standard DP
class HouseRobber {
public int rob(int[] nums) {
if (nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[nums.length - 1];
}
}
// Approach 2: Space Optimized
class HouseRobber {
public int rob(int[] nums) {
if (nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
int prev2 = nums[0];
int prev1 = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
int current = Math.max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = current;
}
return prev1;
}
}
// Approach 3: Recursive with Memoization
class HouseRobber {
public int rob(int[] nums) {
int[] memo = new int[nums.length];
Arrays.fill(memo, -1);
return helper(nums, 0, memo);
}
private int helper(int[] nums, int i, int[] memo) {
if (i >= nums.length) return 0;
if (memo[i] != -1) return memo[i];
// Two choices: rob this house or skip it
int robCurrent = nums[i] + helper(nums, i + 2, memo);
int skipCurrent = helper(nums, i + 1, memo);
memo[i] = Math.max(robCurrent, skipCurrent);
return memo[i];
}
}
```python
# Approach 1: Standard DP
class HouseRobber:
def rob(self, nums):
if not nums:
return 0
if len(nums) == 1:
return nums[0]
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[-1]
# Approach 2: Space Optimized
class HouseRobber:
def rob(self, nums):
if not nums:
return 0
if len(nums) == 1:
return nums[0]
prev2 = nums[0]
prev1 = max(nums[0], nums[1])
for i in range(2, len(nums)):
current = max(prev1, prev2 + nums[i])
prev2 = prev1
prev1 = current
return prev1
# Approach 3: Recursive with Memoization
class HouseRobber:
def rob(self, nums):
memo = {}
def helper(i):
if i >= len(nums):
return 0
if i in memo:
return memo[i]
# Two choices: rob this house or skip it
rob_current = nums[i] + helper(i + 2)
skip_current = helper(i + 1)
memo[i] = max(rob_current, skip_current)
return memo[i]
return helper(0)
```
```javascript
// Approach 1: Standard DP
class HouseRobber {
rob(nums) {
if (nums.length === 0) return 0;
if (nums.length === 1) return nums[0];
const dp = new Array(nums.length);
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (let i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[nums.length - 1];
}
}
// Approach 2: Space Optimized
class HouseRobber {
rob(nums) {
if (nums.length === 0) return 0;
if (nums.length === 1) return nums[0];
let prev2 = nums[0];
let prev1 = Math.max(nums[0], nums[1]);
for (let i = 2; i < nums.length; i++) {
const current = Math.max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = current;
}
return prev1;
}
}
// Approach 3: Recursive with Memoization
class HouseRobber {
rob(nums) {
const memo = new Map();
const helper = (i) => {
if (i >= nums.length) return 0;
if (memo.has(i)) return memo.get(i);
// Two choices: rob this house or skip it
const robCurrent = nums[i] + helper(i + 2);
const skipCurrent = helper(i + 1);
const result = Math.max(robCurrent, skipCurrent);
memo.set(i, result);
return result;
};
return helper(0);
}
}
```
Complexity Analysis:
💭 Think about it, then click to reveal
The key insight is that **you cannot rob both the first and last house** because they are now adjacent in the circle. This creates a mutual exclusion constraint. This means you have two distinct scenarios to consider: - **Scenario 1**: You might rob the first house (so you definitely can't rob the last house) - **Scenario 2**: You might rob the last house (so you definitely can't rob the first house) The circular constraint effectively creates two separate linear problems!💭 Think about it, then click to reveal
Since you can't rob both first and last house, you can break this into two linear House Robber problems: **Subproblem 1**: Rob houses from index 0 to n-2 (exclude the last house) - This ensures if you rob the first house, you won't rob the last house - This is just the regular House Robber problem on a smaller array **Subproblem 2**: Rob houses from index 1 to n-1 (exclude the first house) - This ensures if you rob the last house, you won't rob the first house - This is again the regular House Robber problem on a smaller array **Final answer**: Take the maximum of both subproblems! This demonstrates a powerful problem-solving technique: reducing complex constraints to simpler, known problems.💭 Think about it, then click to reveal
**Edge cases require special handling**: - **1 house**: No circular constraint issue - just rob the single house - **2 houses**: Pick the one with more money (they're adjacent, so you can only rob one) - **3+ houses**: Use the two-subproblem approach For 2 houses, you don't need the complex logic because there are only two choices anyway. **Implementation tip**: Handle small cases explicitly, then use the general algorithm for larger inputs. This pattern of "special cases + general algorithm" is common in DP problems.// Approach 1: Two Linear Robberies
class HouseRobberII {
public int rob(int[] nums) {
if (nums.length == 1) return nums[0];
if (nums.length == 2) return Math.max(nums[0], nums[1]);
// Case 1: Rob houses 0 to n-2 (exclude last)
int robFirst = robLinear(nums, 0, nums.length - 2);
// Case 2: Rob houses 1 to n-1 (exclude first)
int robLast = robLinear(nums, 1, nums.length - 1);
return Math.max(robFirst, robLast);
}
private int robLinear(int[] nums, int start, int end) {
int prev2 = 0, prev1 = 0;
for (int i = start; i <= end; i++) {
int current = Math.max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = current;
}
return prev1;
}
}
// Approach 2: Alternative Implementation
class HouseRobberII {
public int rob(int[] nums) {
if (nums.length == 1) return nums[0];
return Math.max(
robHelper(Arrays.copyOfRange(nums, 0, nums.length - 1)),
robHelper(Arrays.copyOfRange(nums, 1, nums.length))
);
}
private int robHelper(int[] nums) {
int rob = 0, notRob = 0;
for (int num : nums) {
int currRob = notRob + num;
notRob = Math.max(notRob, rob);
rob = currRob;
}
return Math.max(rob, notRob);
}
}
```python
# Approach 1: Two Linear Robberies
class HouseRobberII:
def rob(self, nums):
if len(nums) == 1:
return nums[0]
if len(nums) == 2:
return max(nums[0], nums[1])
# Case 1: Rob houses 0 to n-2 (exclude last)
rob_first = self.rob_linear(nums, 0, len(nums) - 2)
# Case 2: Rob houses 1 to n-1 (exclude first)
rob_last = self.rob_linear(nums, 1, len(nums) - 1)
return max(rob_first, rob_last)
def rob_linear(self, nums, start, end):
prev2, prev1 = 0, 0
for i in range(start, end + 1):
current = max(prev1, prev2 + nums[i])
prev2 = prev1
prev1 = current
return prev1
# Approach 2: Alternative Implementation
class HouseRobberII:
def rob(self, nums):
if len(nums) == 1:
return nums[0]
return max(
self.rob_helper(nums[:-1]), # Exclude last
self.rob_helper(nums[1:]) # Exclude first
)
def rob_helper(self, nums):
rob, not_rob = 0, 0
for num in nums:
curr_rob = not_rob + num
not_rob = max(not_rob, rob)
rob = curr_rob
return max(rob, not_rob)
```
```javascript
// Approach 1: Two Linear Robberies
class HouseRobberII {
rob(nums) {
if (nums.length === 1) return nums[0];
if (nums.length === 2) return Math.max(nums[0], nums[1]);
// Case 1: Rob houses 0 to n-2 (exclude last)
const robFirst = this.robLinear(nums, 0, nums.length - 2);
// Case 2: Rob houses 1 to n-1 (exclude first)
const robLast = this.robLinear(nums, 1, nums.length - 1);
return Math.max(robFirst, robLast);
}
robLinear(nums, start, end) {
let prev2 = 0, prev1 = 0;
for (let i = start; i <= end; i++) {
const current = Math.max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = current;
}
return prev1;
}
}
// Approach 2: Alternative Implementation
class HouseRobberII {
rob(nums) {
if (nums.length === 1) return nums[0];
return Math.max(
this.robHelper(nums.slice(0, -1)), // Exclude last
this.robHelper(nums.slice(1)) // Exclude first
);
}
robHelper(nums) {
let rob = 0, notRob = 0;
for (const num of nums) {
const currRob = notRob + num;
notRob = Math.max(notRob, rob);
rob = currRob;
}
return Math.max(rob, notRob);
}
}
```
Complexity Analysis:
💭 Think about it, then click to reveal
For "12", there are two valid decodings: 1. "1" + "2" → "A" + "B" → "AB" 2. "12" → "L" → "L" **Validity rules**: - Single digit: Must be 1-9 (not 0) - Two digits: Must be 10-26 At each position, you're essentially asking: "Can I decode this character by itself? Can I decode it together with the previous character?" This choice pattern suggests a DP approach where each decision affects future possibilities.💭 Think about it, then click to reveal
At position i, you have up to two ways to extend previous decodings: **Option 1 - Single digit decoding**: - If s[i] is valid (1-9), you can extend all decodings ending at i-1 - Add: `dp[i-1]` ways **Option 2 - Two digit decoding**: - If s[i-1:i+1] is valid (10-26), you can extend all decodings ending at i-2 - Add: `dp[i-2]` ways **Recurrence**: `dp[i] = (valid_single ? dp[i-1] : 0) + (valid_double ? dp[i-2] : 0)` This is similar to Fibonacci, but with conditional additions based on digit validity!💭 Think about it, then click to reveal
**Critical edge cases**: 1. **Leading zero**: If string starts with '0', it's impossible to decode → return 0 2. **Isolated zero**: A '0' can only be part of "10" or "20", never by itself 3. **Invalid two-digit**: Numbers > 26 cannot be decoded as two digits **Base cases**: - `dp[0] = 1` (empty string has one way to decode: decode nothing) - `dp[1] = 1` if first character is valid, otherwise 0 **String handling**: Be careful with 0-based vs 1-based indexing when checking `s[i-1]` for digit validity. The key insight: '0' creates constraints - it can only appear as the second digit in "10" or "20".// Approach 1: Standard DP
class DecodeWays {
public int numDecodings(String s) {
if (s == null || s.length() == 0 || s.charAt(0) == '0') {
return 0;
}
int n = s.length();
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
// Single digit
if (s.charAt(i - 1) != '0') {
dp[i] += dp[i - 1];
}
// Two digits
int twoDigit = Integer.parseInt(s.substring(i - 2, i));
if (twoDigit >= 10 && twoDigit <= 26) {
dp[i] += dp[i - 2];
}
}
return dp[n];
}
}
// Approach 2: Space Optimized
class DecodeWays {
public int numDecodings(String s) {
if (s == null || s.length() == 0 || s.charAt(0) == '0') {
return 0;
}
int prev2 = 1, prev1 = 1;
for (int i = 1; i < s.length(); i++) {
int current = 0;
// Single digit
if (s.charAt(i) != '0') {
current += prev1;
}
// Two digits
int twoDigit = Integer.parseInt(s.substring(i - 1, i + 1));
if (twoDigit >= 10 && twoDigit <= 26) {
current += prev2;
}
prev2 = prev1;
prev1 = current;
}
return prev1;
}
}
// Approach 3: Recursive with Memoization
class DecodeWays {
public int numDecodings(String s) {
Integer[] memo = new Integer[s.length()];
return helper(s, 0, memo);
}
private int helper(String s, int index, Integer[] memo) {
if (index == s.length()) return 1;
if (s.charAt(index) == '0') return 0;
if (memo[index] != null) return memo[index];
int result = helper(s, index + 1, memo);
if (index + 1 < s.length()) {
int twoDigit = Integer.parseInt(s.substring(index, index + 2));
if (twoDigit <= 26) {
result += helper(s, index + 2, memo);
}
}
memo[index] = result;
return result;
}
}
```python
# Approach 1: Standard DP
class DecodeWays:
def numDecodings(self, s: str) -> int:
if not s or s[0] == '0':
return 0
n = len(s)
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
# Single digit
if s[i - 1] != '0':
dp[i] += dp[i - 1]
# Two digits
two_digit = int(s[i - 2:i])
if 10 <= two_digit <= 26:
dp[i] += dp[i - 2]
return dp[n]
# Approach 2: Space Optimized
class DecodeWays:
def numDecodings(self, s: str) -> int:
if not s or s[0] == '0':
return 0
prev2, prev1 = 1, 1
for i in range(1, len(s)):
current = 0
# Single digit
if s[i] != '0':
current += prev1
# Two digits
two_digit = int(s[i - 1:i + 1])
if 10 <= two_digit <= 26:
current += prev2
prev2 = prev1
prev1 = current
return prev1
# Approach 3: Recursive with Memoization
class DecodeWays:
def numDecodings(self, s: str) -> int:
memo = {}
def helper(index):
if index == len(s):
return 1
if s[index] == '0':
return 0
if index in memo:
return memo[index]
result = helper(index + 1)
if index + 1 < len(s):
two_digit = int(s[index:index + 2])
if two_digit <= 26:
result += helper(index + 2)
memo[index] = result
return result
return helper(0)
```
```javascript
// Approach 1: Standard DP
class DecodeWays {
numDecodings(s) {
if (!s || s.length === 0 || s[0] === '0') {
return 0;
}
const n = s.length;
const dp = new Array(n + 1).fill(0);
dp[0] = 1;
dp[1] = 1;
for (let i = 2; i <= n; i++) {
// Single digit
if (s[i - 1] !== '0') {
dp[i] += dp[i - 1];
}
// Two digits
const twoDigit = parseInt(s.substring(i - 2, i));
if (twoDigit >= 10 && twoDigit <= 26) {
dp[i] += dp[i - 2];
}
}
return dp[n];
}
}
// Approach 2: Space Optimized
class DecodeWays {
numDecodings(s) {
if (!s || s.length === 0 || s[0] === '0') {
return 0;
}
let prev2 = 1, prev1 = 1;
for (let i = 1; i < s.length; i++) {
let current = 0;
// Single digit
if (s[i] !== '0') {
current += prev1;
}
// Two digits
const twoDigit = parseInt(s.substring(i - 1, i + 1));
if (twoDigit >= 10 && twoDigit <= 26) {
current += prev2;
}
prev2 = prev1;
prev1 = current;
}
return prev1;
}
}
// Approach 3: Recursive with Memoization
class DecodeWays {
numDecodings(s) {
const memo = new Map();
const helper = (index) => {
if (index === s.length) return 1;
if (s[index] === '0') return 0;
if (memo.has(index)) return memo.get(index);
let result = helper(index + 1);
if (index + 1 < s.length) {
const twoDigit = parseInt(s.substring(index, index + 2));
if (twoDigit <= 26) {
result += helper(index + 2);
}
}
memo.set(index, result);
return result;
};
return helper(0);
}
}
```
Complexity Analysis:
Key Insights & Patterns:
💭 Think about it, then click to reveal
Since the robot can only move right or down, to reach any cell (i,j), the robot must have come from either: - Cell (i-1,j) by moving down, OR - Cell (i,j-1) by moving right This creates a perfect subproblem structure: the number of ways to reach (i,j) equals the sum of ways to reach the two possible previous positions. **Key insight**: This constraint eliminates cycles and creates a dependency graph that naturally fits DP. No cell can be reached in multiple different ways from the same starting position.💭 Think about it, then click to reveal
**DP Approach**: `dp[i][j] = dp[i-1][j] + dp[i][j-1]` with base cases dp[0][j] = dp[i][0] = 1. **Mathematical Insight**: - To reach (m-1, n-1) from (0,0), robot makes exactly (m-1) down moves and (n-1) right moves - Total moves = (m-1) + (n-1) = m+n-2 - Question becomes: "In how many ways can you arrange (m-1) down moves among (m+n-2) total moves?" - Answer: C(m+n-2, m-1) = (m+n-2)! / ((m-1)! × (n-1)!) The DP approach builds this combination step by step, while the mathematical approach calculates it directly.💭 Think about it, then click to reveal
Since dp[i][j] only depends on dp[i-1][j] (directly above) and dp[i][j-1] (directly left), you only need to store one row at a time. **Space optimization pattern**: - Use 1D array where dp[j] represents paths to column j in current row - When processing column j: dp[j] = dp[j] + dp[j-1] - dp[j] (before update) = paths from above - dp[j-1] = paths from left - dp[j] (after update) = total paths to current cell This reduces space from O(m×n) to O(min(m,n)) by processing the grid row by row. **Pro tip**: Always optimize along the smaller dimension to minimize space usage.// Approach 1: 2D DP
class UniquePaths {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
// Initialize first row and column
for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;
// Fill the dp table
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
}
// Approach 2: Space Optimized (1D DP)
class UniquePaths {
public int uniquePaths(int m, int n) {
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] += dp[j - 1];
}
}
return dp[n - 1];
}
}
// Approach 3: Mathematical Solution (Combinations)
class UniquePaths {
public int uniquePaths(int m, int n) {
// Total moves: (m-1) down + (n-1) right = m+n-2
// Choose (m-1) positions for down moves: C(m+n-2, m-1)
long result = 1;
int moves = m + n - 2;
int down = m - 1;
for (int i = 1; i <= down; i++) {
result = result * (moves - down + i) / i;
}
return (int) result;
}
}
```python
# Approach 1: 2D DP
class UniquePaths:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[1] * n for _ in range(m)]
# First row and column are already initialized to 1
# Fill the dp table
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m - 1][n - 1]
# Approach 2: Space Optimized (1D DP)
class UniquePaths:
def uniquePaths(self, m: int, n: int) -> int:
dp = [1] * n
for i in range(1, m):
for j in range(1, n):
dp[j] += dp[j - 1]
return dp[n - 1]
# Approach 3: Mathematical Solution (Combinations)
class UniquePaths:
def uniquePaths(self, m: int, n: int) -> int:
# Total moves: (m-1) down + (n-1) right = m+n-2
# Choose (m-1) positions for down moves: C(m+n-2, m-1)
from math import comb
return comb(m + n - 2, m - 1)
# Alternative without using comb function
def uniquePathsManual(self, m: int, n: int) -> int:
result = 1
moves = m + n - 2
down = m - 1
for i in range(1, down + 1):
result = result * (moves - down + i) // i
return result
```
```javascript
// Approach 1: 2D DP
class UniquePaths {
uniquePaths(m, n) {
const dp = Array(m).fill().map(() => Array(n).fill(1));
// First row and column are already initialized to 1
// Fill the dp table
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
}
// Approach 2: Space Optimized (1D DP)
class UniquePaths {
uniquePaths(m, n) {
const dp = new Array(n).fill(1);
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[j] += dp[j - 1];
}
}
return dp[n - 1];
}
}
// Approach 3: Mathematical Solution (Combinations)
class UniquePaths {
uniquePaths(m, n) {
// Total moves: (m-1) down + (n-1) right = m+n-2
// Choose (m-1) positions for down moves: C(m+n-2, m-1)
let result = 1;
const moves = m + n - 2;
const down = m - 1;
for (let i = 1; i <= down; i++) {
result = Math.floor(result * (moves - down + i) / i);
}
return result;
}
}
```
Complexity Analysis:
💭 Think about it, then click to reveal
A position i is reachable if: - It's the starting position (position 0), OR - There exists some reachable position j < i where j + nums[j] >= i This creates a DP formulation: `dp[i] = true` if there exists any j < i where `dp[j] = true AND j + nums[j] >= i` The insight: reachability propagates forward. If you can reach position j, you can reach any position within nums[j] steps from j. This is a **boolean DP** problem - you're checking possibility, not optimizing a value.💭 Think about it, then click to reveal
**DP Approach (O(n²))**: For each position, check all previous positions to see if any can reach it. **Greedy Approach (O(n))**: Track `maxReach` = farthest position reachable so far. - At position i: if i > maxReach, it's unreachable → return false - Otherwise: update maxReach = max(maxReach, i + nums[i]) - If maxReach >= lastIndex, we can reach the end → return true **Key insight**: You don't need to track exactly how to reach each position, just whether it's reachable. The greedy approach works because if you can reach position i, and i can reach further than your current max, then i becomes your new "best option." This demonstrates that **sometimes greedy algorithms are optimal even when DP seems natural**.💭 Think about it, then click to reveal
**Backward DP approach**: - Start from the last position (which can trivially "reach" the end) - For each position going backward, check if it can jump to any "good" position - A position is "good" if it can eventually reach the end **Algorithm**: ``` lastGoodIndex = n-1 for i from n-2 to 0: if i + nums[i] >= lastGoodIndex: lastGoodIndex = i return lastGoodIndex == 0 ``` This is another O(n) solution that's conceptually different from the greedy approach but equally efficient. **Pattern recognition**: Many DP problems can be solved both forward and backward - sometimes one direction is more intuitive or efficient.// Approach 1: DP Solution
class JumpGame {
public boolean canJump(int[] nums) {
boolean[] dp = new boolean[nums.length];
dp[0] = true;
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && j + nums[j] >= i) {
dp[i] = true;
break;
}
}
}
return dp[nums.length - 1];
}
}
// Approach 2: Greedy Solution (More Efficient)
class JumpGame {
public boolean canJump(int[] nums) {
int maxReach = 0;
for (int i = 0; i < nums.length; i++) {
if (i > maxReach) return false;
maxReach = Math.max(maxReach, i + nums[i]);
if (maxReach >= nums.length - 1) return true;
}
return true;
}
}
// Approach 3: Backward DP
class JumpGame {
public boolean canJump(int[] nums) {
int lastGoodIndex = nums.length - 1;
for (int i = nums.length - 2; i >= 0; i--) {
if (i + nums[i] >= lastGoodIndex) {
lastGoodIndex = i;
}
}
return lastGoodIndex == 0;
}
}
// Approach 4: Recursive with Memoization
class JumpGame {
public boolean canJump(int[] nums) {
Boolean[] memo = new Boolean[nums.length];
return helper(nums, 0, memo);
}
private boolean helper(int[] nums, int pos, Boolean[] memo) {
if (pos >= nums.length - 1) return true;
if (memo[pos] != null) return memo[pos];
int maxJump = Math.min(pos + nums[pos], nums.length - 1);
for (int nextPos = pos + 1; nextPos <= maxJump; nextPos++) {
if (helper(nums, nextPos, memo)) {
memo[pos] = true;
return true;
}
}
memo[pos] = false;
return false;
}
}
```python
# Approach 1: DP Solution
class JumpGame:
def canJump(self, nums):
dp = [False] * len(nums)
dp[0] = True
for i in range(1, len(nums)):
for j in range(i):
if dp[j] and j + nums[j] >= i:
dp[i] = True
break
return dp[-1]
# Approach 2: Greedy Solution (More Efficient)
class JumpGame:
def canJump(self, nums):
max_reach = 0
for i in range(len(nums)):
if i > max_reach:
return False
max_reach = max(max_reach, i + nums[i])
if max_reach >= len(nums) - 1:
return True
return True
# Approach 3: Backward DP
class JumpGame:
def canJump(self, nums):
last_good_index = len(nums) - 1
for i in range(len(nums) - 2, -1, -1):
if i + nums[i] >= last_good_index:
last_good_index = i
return last_good_index == 0
# Approach 4: Recursive with Memoization
class JumpGame:
def canJump(self, nums):
memo = {}
def helper(pos):
if pos >= len(nums) - 1:
return True
if pos in memo:
return memo[pos]
max_jump = min(pos + nums[pos], len(nums) - 1)
for next_pos in range(pos + 1, max_jump + 1):
if helper(next_pos):
memo[pos] = True
return True
memo[pos] = False
return False
return helper(0)
```
```javascript
// Approach 1: DP Solution
class JumpGame {
canJump(nums) {
const dp = new Array(nums.length).fill(false);
dp[0] = true;
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (dp[j] && j + nums[j] >= i) {
dp[i] = true;
break;
}
}
}
return dp[nums.length - 1];
}
}
// Approach 2: Greedy Solution (More Efficient)
class JumpGame {
canJump(nums) {
let maxReach = 0;
for (let i = 0; i < nums.length; i++) {
if (i > maxReach) return false;
maxReach = Math.max(maxReach, i + nums[i]);
if (maxReach >= nums.length - 1) return true;
}
return true;
}
}
// Approach 3: Backward DP
class JumpGame {
canJump(nums) {
let lastGoodIndex = nums.length - 1;
for (let i = nums.length - 2; i >= 0; i--) {
if (i + nums[i] >= lastGoodIndex) {
lastGoodIndex = i;
}
}
return lastGoodIndex === 0;
}
}
// Approach 4: Recursive with Memoization
class JumpGame {
canJump(nums) {
const memo = new Map();
const helper = (pos) => {
if (pos >= nums.length - 1) return true;
if (memo.has(pos)) return memo.get(pos);
const maxJump = Math.min(pos + nums[pos], nums.length - 1);
for (let nextPos = pos + 1; nextPos <= maxJump; nextPos++) {
if (helper(nextPos)) {
memo.set(pos, true);
return true;
}
}
memo.set(pos, false);
return false;
};
return helper(0);
}
}
```
Complexity Analysis:
// Instead of: dp[i] = dp[i-1] + dp[i-2]
int prev2 = dp[0], prev1 = dp[1];
for (int i = 2; i <= n; i++) {
int current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
// Instead of: dp[i][j] = dp[i-1][j] + dp[i][j-1]
int[] dp = new int[n];
for (int i = 0; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[j] += dp[j-1];
}
}
// Use original array as DP table if constraints allow
for (int i = 1; i < nums.length; i++) {
nums[i] = Math.max(nums[i-1], nums[i-2] + nums[i]);
}
int a = 0, b = 1;
for (int i = 2; i <= n; i++) {
int temp = a + b;
a = b;
b = temp;
}