DSA: Dynamic Programming Classic Problems
Master the canonical DP patterns: knapsack, subset problems, coin change, and rod cutting.
0/1 Knapsack Problem
Given n items each with a weight and value, and a knapsack of capacity W, find the maximum value you can carry. Each item is either taken (1) or skipped (0).
0/1 Knapsack
dp[i][w] = max value using first i items with capacity w.
- Skip item i: dp[i][w] = dp[i-1][w]
- Take item i (if weight fits): dp[i][w] = val[i] + dp[i-1][w - wt[i]]
- Recurrence: dp[i][w] = max(skip, take)
- Time: O(n * W), Space: O(n * W) or O(W) with 1D optimization
0/1 Knapsack (Tabulation)
C++2D DP table: rows = items, columns = capacity.
Unbounded Knapsack
Same setup as 0/1 Knapsack but each item can be used unlimited times. The key difference is that when taking item i, we stay on rowi instead of moving toi-1.
Unbounded Knapsack
1D DP suffices: dp[w] = max value for capacity w, items reusable.
- Recurrence: dp[w] = max(dp[w], val[i] + dp[w - wt[i]]) for each item
- Iterate capacity w from wt[i] to W (left to right allows reuse)
- 0/1 Knapsack iterates w right-to-left to prevent reuse
- Time: O(n * W), Space: O(W)
Unbounded Knapsack
C++1D DP with left-to-right traversal to allow item reuse.
Subset Sum Problem
Determine if any subset of a given array sums exactly to a target value. This is a decision variant of the knapsack pattern.
Subset Sum
dp[i][s] = true if subset of first i elements sums to s.
- Base case: dp[i][0] = true for all i (empty subset sums to 0)
- Skip: dp[i][s] = dp[i-1][s]
- Include: dp[i][s] = dp[i-1][s - arr[i-1]] if arr[i-1] <= s
- Answer: dp[n][target]
Subset Sum
C++Boolean DP table to check if any subset reaches the target.
Equal Sum Partition
Determine if an array can be split into two subsets with equal sum. Reduces directly to Subset Sum with target = totalSum / 2.
Equal Sum Partition
If totalSum is odd, partition is impossible. Otherwise check subsetSum(arr, totalSum/2).
- Odd total sum: impossible (two equal integers cannot sum to an odd number)
- Even total sum: find subset summing to totalSum / 2
- Reuses Subset Sum DP directly
- Common interview pattern: recognize the reduction to Subset Sum
Equal Sum Partition
C++Reduce to Subset Sum with target = totalSum / 2.
Minimum Subset Sum Difference
Partition an array into two subsets to minimize the absolute difference between their sums. Use the last row of the Subset Sum DP table to find all reachable sums.
Min Subset Sum Difference
After Subset Sum DP, scan reachable sums S in [0, total/2]. Answer = min(total - 2*S).
- If subset sum S is reachable, the other subset sum = total - S
- Difference = |S - (total - S)| = total - 2*S (since S <= total/2)
- Check only S up to total/2 to avoid duplicate comparisons
- Time: O(n * totalSum), Space: O(n * totalSum)
Minimum Subset Sum Difference
C++Scan last DP row to find the closest reachable sum to total/2.
Count Subsets with Given Sum
Count how many subsets of an array sum exactly to a given target. Changes the boolean DP to an integer count DP.
Count Subset Sum
dp[i][s] = number of subsets of first i elements summing to s.
- Base case: dp[i][0] = 1 for all i (empty subset always counts)
- Recurrence: dp[i][s] = dp[i-1][s] + dp[i-1][s - arr[i-1]]
- Additive instead of boolean OR from Subset Sum
- Used as a building block for Target Sum (assign +/-) problems
Count Subsets with Given Sum
C++Integer DP instead of boolean: accumulate counts of valid subsets.
Coin Change: Count Ways
Given coin denominations and an amount, count the total number of ways to make that amount. Coins can be reused (unbounded), so this is structurally Unbounded Knapsack with counting.
Coin Change (Ways)
dp[s] = number of ways to make amount s using available coins.
- Base case: dp[0] = 1 (one way to make 0: use no coins)
- For each coin, iterate amount left to right to allow reuse
- Recurrence: dp[s] += dp[s - coin]
- Order matters for counting: iterate coins in outer loop for combinations
Coin Change: Count Ways
C++Count distinct combinations of coins that sum to the target amount.
Coin Change: Minimum Coins
Find the fewest number of coins needed to make a given amount. Uses a minimization DP instead of counting.
Coin Change (Min Coins)
dp[s] = minimum coins to make amount s. Initialize to infinity, base dp[0] = 0.
- Base case: dp[0] = 0
- Recurrence: dp[s] = min(dp[s], dp[s - coin] + 1)
- If dp[amount] is still infinity after filling, amount is unreachable
- Time: O(amount * n), Space: O(amount)
Coin Change: Minimum Coins
C++Minimize coin count using a DP array initialized to infinity.
Rod Cutting Problem
Given a rod of length n and a price table for each length, find the maximum revenue from cutting the rod into pieces. This is structurally identical to Unbounded Knapsack.
Rod Cutting
dp[len] = max revenue for rod of length len. Each cut length is an item that can be reused.
- Item i: cut of length i with price[i]
- Recurrence: dp[len] = max(dp[len], price[i] + dp[len - i]) for i in 1..len
- Identical to Unbounded Knapsack with wt[i] = i, val[i] = price[i]
- Time: O(n²), Space: O(n)
Rod Cutting
C++Maximize revenue by trying every possible first cut at each length.
Problem Pattern Map
All classic DP problems on this page map to one of three base patterns.
| Problem | Base Pattern | DP Value Type | Item Reuse |
|---|---|---|---|
| 0/1 Knapsack | Knapsack | max integer | No |
| Unbounded Knapsack | Knapsack | max integer | Yes |
| Subset Sum | Knapsack | boolean | No |
| Equal Sum Partition | Subset Sum | boolean | No |
| Min Subset Diff | Subset Sum | boolean + scan | No |
| Count Subsets | Subset Sum | count integer | No |
| Coin Change (ways) | Unbounded Knapsack | count integer | Yes |
| Coin Change (min) | Unbounded Knapsack | min integer | Yes |
| Rod Cutting | Unbounded Knapsack | max integer | Yes |
Knowledge Check
1. In the 0/1 Knapsack problem, why is each item considered at most once?
2. What distinguishes Unbounded Knapsack from 0/1 Knapsack?
3. The Subset Sum problem asks:
4. Equal Sum Partition is possible when:
5. In Coin Change (minimum coins), what does dp[i] represent?
6. The recurrence for Coin Change (minimum coins) is:
7. Rod Cutting DP is structurally identical to:
8. Minimum Subset Sum Difference formula (using last row of Subset Sum DP) is: