Thirteen problems that drill 1-D dynamic programming from Lesson 17. The hard 90% of every one of these is finding the recurrence — so for each, write down what dp[i] means before you write any code. Each solution here was actually run and tested.
How to practise. Force yourself to state the recurrence in one line before coding (e.g. “rob[i] = max(skip, rob[i-2] + nums[i])”). If you can’t, you haven’t understood the problem yet — don’t start typing. Then code bottom-up, and only afterwards compress to O(1) space where the pattern allows.
The 13 problems
- 1Climbing Stairs (LeetCode 70)EasyCount the ways to climb n steps taking 1 or 2 at a time: the answer is Fibonacci, kept in two variables.arrow_forward
- 2Min Cost Climbing Stairs (LeetCode 746)EasyFind the cheapest way to the top when each step has a cost: take the min of the two ways to arrive.arrow_forward
- 3Maximum Subarray (LeetCode 53)MediumFind the contiguous subarray with the largest sum: at each element, extend the run or start fresh.arrow_forward
- 4House Robber (LeetCode 198)MediumMaximise loot without robbing two adjacent houses: at each house, take the better of skip or rob.arrow_forward
- 5House Robber II (LeetCode 213)MediumHouse Robber on a circle: run the linear version without the first house and without the last, take the max.arrow_forward
- 6Jump Game (LeetCode 55)MediumCan you reach the last index? Track the furthest index reachable so far; if you step past it, you're stuck.arrow_forward
- 7Coin Change (LeetCode 322)MediumFewest coins to make an amount: dp[a] is the best for amount a, built from dp[a - coin] + 1.arrow_forward
- 8Coin Change II (LeetCode 518)MediumCount coin combinations that make an amount: loop coins on the outside so each combination counts once.arrow_forward
- 9Word Break (LeetCode 139)MediumCan a string be split into dictionary words? dp[i] is true if some split j has dp[j] and s[j:i] a word.arrow_forward
- 10Decode Ways (LeetCode 91)MediumCount ways to decode a digit string as letters (1=A … 26=Z): Climbing Stairs with validity checks.arrow_forward
- 11Maximum Product Subarray (LeetCode 152)MediumLargest product of a contiguous subarray: track the max and min product ending here, since negatives flip.arrow_forward
- 12Longest Increasing Subsequence (LeetCode 300)MediumLongest strictly increasing subsequence: keep the smallest tail for each length and binary-search into it.arrow_forward
- 13Partition Equal Subset Sum (LeetCode 416)MediumSplit an array into two equal-sum halves: ask whether any subset reaches total/2, tracking reachable sums.arrow_forward