Dynamic Programming Exercises: Practice Problems (with Solutions)
Time to build DP intuition the only way that works — by solving. For each problem, define the state, the transition, and the base cases before you write a line of code, then trace a tiny example by hand. Only then open the answer. Every View answer link jumps to a full, multi-language solution on the DP solutions page.
How to practice: For each problem, say out loud “
dp[i]means ___.” If you can finish that sentence, the recurrence usually follows. Re-read the DP introduction if you get stuck on framing.
Warm-ups
Q1. Min Cost Climbing Stairs. Given cost[] where cost[i] is the price of stepping on stair i, you climb 1 or 2 steps at a time and may start at index 0 or 1. Return the minimum cost to reach the top (just past the last stair). Target O(n) time, O(1) space.
Q2. House Robber. Given nums[] of house values along a street, rob the maximum total without robbing two adjacent houses. Target O(n) time, O(1) space.
Core problems
Q3. Partition Equal Subset Sum. Given an array of positive integers, decide whether it can be split into two subsets with equal sum. Target O(n·S) time where S is the total sum.
Q4. Longest Palindromic Subsequence. Given a string, return the length of its longest subsequence that reads the same forward and backward. Target O(n²).
Q5. Coin Change (minimum coins). Given coin denominations (unlimited supply) and an amount, return the fewest coins that sum to it, or -1 if impossible. Target O(amount · coins).
Challenge
Q6. Word Break. Given a string s and a dictionary of words, decide whether s can be segmented into a space-separated sequence of dictionary words. Target O(n²) (plus substring/lookup cost).
Q7. Maximum Product Subarray. Given an integer array (which may contain negatives and zeros), return the largest product of any contiguous subarray. Target a single O(n) pass.
Done? Review every solution on the DP answer sheet — even the ones you solved, since DP often has a cleaner state. Then explore higher-level dynamic programming patterns.