Dynamic Programming Coding Problems: 195 Questions with Solutions

How dynamic programming works, step by step

1. No two neighbouring houses can both be robbed. Let dp[i] be the most money from houses 0..i: either skip house i and keep dp[i−1], or rob it and add nums[i] to dp[i−2], the best that leaves house i−1 alone.
2. dp[0] = 2: with a single house, rob it. This is the base case every later cell builds on.
3. dp[1] = max(dp[0], nums[1]) = max(2, 7) = 7: houses 0 and 1 are neighbours, so take the richer one, house 1.
4. dp[2] = max(skip: 7, rob: 2 + 9 = 11) = 11. Robbing house 2 wins, so the best plan so far ends with house 2.
5. dp[3] = max(skip: 11, rob: 7 + 3 = 10) = 11. Skipping wins: house 3 is worth less than what robbing it would give up.
6. dp[4] = max(skip: 11, rob: 11 + 1 = 12) = 12. Robbing house 4 wins, so the best plan so far ends with house 4.
7. The answer is dp[4] = 12. Walking back, a house was robbed wherever dp changes from its left neighbour: houses 0, 2 and 4, 2 + 9 + 1 = 12. One pass, O(n) time, and O(1) space keeping only the last two cells.

Dynamic Programming study plan

14 of the 195 Dynamic Programming problems (4 easy, 7 medium and 3 hard) over 8 days, about 8 h 10 min in all — the pattern first, then easiest to hardest. After that, the other 181 in the full list below are practice at your own pace. Then move on to Memoization.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 3.

• Best Time to Buy and Sell Stock Easy
• Is Subsequence Easy
• Counting Bits Easy

Day 2

Medium problems: the same pattern with one twist each. Name the twist before you code.

• Climbing Stairs Easy
• Maximum Subarray Medium

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

• Longest Palindromic Substring Medium
• Jump Game Medium

Day 4

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

• Ugly Number II Medium
• Generate Parentheses Medium

Day 5

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

• Target Sum Medium
• Cheapest Flights Within K Stops Medium

Day 6

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

• Trapping Rain Water Hard

Day 7

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

• Regular Expression Matching Hard

Day 8

Another hard one. If it beats you after a real attempt, read the editorial, then solve it again tomorrow from memory.

• Best Time to Buy and Sell Stock III Hard

Next topic: Memoization

Dynamic Programming: the essentials

When to reach for it

The question asks for a count of ways, a minimum or maximum cost, or whether something is achievable — and a choice made now changes what is possible later. If a brute-force recursion would solve the same subproblem many times (the same index, the same remaining amount, the same pair of prefixes), the subproblems overlap and DP applies. "Return every way" is different: listing answers is Backtracking.

The pattern

Write the recursion first, over a small state: f(i) for the best answer on the first i items, f(i, j) for two prefixes, f(a) for a remaining amount. Base cases are the states you can answer without recursing. Then memoise it (top-down) or fill a table in an order where every dependency is computed before it is read (bottom-up).

def coin_change(coins, amount):
    INF = amount + 1
    dp = [0] + [INF] * amount       # dp[a] = fewest coins making a
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] <= amount else -1

Cost

States × work per state for time, and the number of states for space — often cut to one or two rows, because a row reads only the one before it. Coin change above is O(amount × coins) time and O(amount) space.

Common mistakes

• A state that leaves out something the future depends on, such as whether you hold a stock or how many transactions remain.
• Filling cells in an order that reads one not yet computed.
• In counting problems, swapping the loops: coins outside counts combinations, amounts outside counts ordered sequences.
• Using 0 to mean "impossible" in a minimisation, or recursing without a memo and paying exponential time.

Start with

• Climbing Stairs: a one-dimensional recurrence.
• House Robber: a take-or-skip choice at each index.
• Coin Change: a table indexed by remaining amount.

All dynamic programming problems

Easy (10)

• Counting Bits Bit Manipulation
• Divisor Game Math, Brainteaser, Game Theory
• Pascal's Triangle II Array
• N-th Tribonacci Number Math, Memoization
• Fibonacci Number Math, Recursion
• Pascal's Triangle Array
• Min Cost Climbing Stairs Array
• Is Subsequence String, Two Pointers
• Best Time to Buy and Sell Stock Array
• Climbing Stairs Math, Memoization

Medium (110)

• Minimum Number of Increments on Subarrays to Form a Target Array Array, Greedy, Stack
• Partition Array for Maximum Sum Array
• Stone Game VII Array, Math, Game Theory
• Minimum Number of Work Sessions to Finish the Tasks Array, Bit Manipulation, Bitmask
• Count Fertile Pyramids in a Land Array, Matrix
• Number of Ways to Divide a Long Corridor Math, String
• Maximum Number of Non-overlapping Palindrome Substrings String, Greedy
• Count Number of Ways to Place Houses Math
• Count Number of Texts Hash Table, Math, String
• Number of Ways to Reach a Position After Exactly k Steps Math, Combinatorics
• Minimum Deletions to Make String Balanced String, Stack
• Number of Ways to Arrive at Destination Graph, Shortest Path, Topological Sort
• Largest Plus Sign Array, Matrix
• Number of Corner Rectangles Array, Matrix, Math
• Maximum Number of Moves in a Grid Array, Matrix, Breadth-First Search
• Minimum Cost Tree From Leaf Values Array, Stack, Monotonic Stack
• The Number of Beautiful Subsets Array, Hash Table, Backtracking
• Longest Binary Subsequence Less Than or Equal to K String, Greedy, Memoization
• Number of Ways to Select Buildings String, Prefix Sum
• Number of People Aware of a Secret Queue, Simulation
• Longest Ideal Subsequence Hash Table, String
• Stone Game II Array, Prefix Sum, Game Theory
• Predict the Winner Array, Recursion, Game Theory
• Count Alternating Subarrays Array, Math
• Count Ways To Build Good Strings
• Longest Arithmetic Subsequence Array, Hash Table, Binary Search
• Coin Change II Array
• Minimum Additions to Make Valid String String, Greedy, Stack
• Partition String Into Substrings With Values at Most K String, Greedy
• Video Stitching Array, Greedy, Intervals
• Max Consecutive Ones II Array, Sliding Window
• Push Dominoes String, Two Pointers, Simulation
• Longest Mountain in Array Array, Two Pointers
• Bitwise ORs of Subarrays Bit Manipulation, Array
• Flip String to Monotone Increasing String, Bit Manipulation
• Super Ugly Number Math, Heap
• Integer Replacement Bit Manipulation, Greedy
• Minimum Operations to Reduce an Integer to 0 Bit Manipulation, Greedy
• Count Substrings That Differ by One Character String
• Count Number of Teams Array
• Uncrossed Lines Array
• Minimum ASCII Delete Sum for Two Strings String
• Longest Palindromic Subsequence String
• Unique Binary Search Trees Math
• Domino and Tromino Tiling
• Paint House Array
• Paint Fence
• As Far from Land as Possible Array, Breadth-First Search, Matrix
• Rotate Function Array, Math
• Sort Integers by The Power Value Memoization, Sorting
• Sum of Subarray Minimums Array, Stack, Monotonic Stack
• Minimum Time to Make Rope Colorful Array, String, Greedy
• Knight Dialer
• 2 Keys Keyboard Math
• Maximum Length of Pair Chain Array, Greedy, Sorting
• Longest Turbulent Subarray Array, Sliding Window
• Number of Dice Rolls With Target Sum
• Best Sightseeing Pair Array
• Maximum Sum Circular Subarray Array, Divide and Conquer, Queue
• Minimum Cost For Tickets Array
• Longest String Chain Array, Hash Table, Two Pointers
• Combination Sum IV Array
• Ones and Zeroes Array, String
• Last Stone Weight II Array
• Stone Game Array, Math, Game Theory
• Count Numbers with Unique Digits Math, Backtracking
• Ugly Number II Hash Table, Math, Heap
• Integer Break Math
• Perfect Squares Math, Breadth-First Search
• Triangle Array
• Minimum Falling Path Sum Array, Matrix
• Interleaving String String
• Delete Operation for Two Strings String
• Count Sorted Vowel Strings Math, Combinatorics
• Arithmetic Slices Array
• Wiggle Subsequence Array, Greedy
• Number of Longest Increasing Subsequence Array, Binary Indexed Tree
• Longest Arithmetic Subsequence of Given Difference Array, Hash Table
• Maximum Length of Repeated Subarray Array, Binary Search, Sliding Window
• Best Time to Buy and Sell Stock with Transaction Fee Array, Greedy
• Best Time to Buy and Sell Stock with Cooldown Array
• Delete and Earn Array, Hash Table
• Count Square Submatrices with All Ones Array, Matrix
• Maximal Square Array, Matrix
• Unique Paths II Array, Matrix
• Minimum Path Sum Array, Matrix
• Longest Subarray of 1's After Deleting One Element Array, Sliding Window
• Valid Parenthesis String String, Stack, Greedy
• Generate Parentheses String, Backtracking
• Cheapest Flights Within K Stops Graph, Shortest Path
• 01 Matrix Array, Matrix, Breadth-First Search
• Target Sum Array, Backtracking
• Edit Distance String
• Longest Common Subsequence String
• Partition Equal Subset Sum Array
• Unique Paths Math, Combinatorics
• Decode Ways String
• Word Break String, Hash Table, Trie
• Longest Increasing Subsequence Array, Binary Search
• Coin Change II Array
• Coin Change Array, Breadth-First Search
• House Robber II Array
• House Robber Array
• Best Time to Buy and Sell Stock II Array, Greedy
• Jump Game II Array, Greedy
• Jump Game Array, Greedy
• Palindromic Substrings String
• Longest Palindromic Substring String
• Maximum Product Subarray Array
• Maximum Subarray Array, Divide and Conquer

Hard (75)

• Count Ways to Make Array With Product Array, Math, Combinatorics
• Count the Number of Ideal Arrays Math, Combinatorics, Number Theory
• Number of Ways to Rearrange Sticks With K Sticks Visible Math, Combinatorics
• The Number of Good Subsets Array, Math, Bit Manipulation
• Number of Ways to Reorder Array to Get Same BST Array, Math, Divide and Conquer
• Make Array Strictly Increasing Array, Binary Search, Sorting
• Odd Even Jump Array, Stack, Monotonic Stack
• Maximum Number of Events That Can Be Attended II Array, Binary Search, Sorting
• Painting the Walls Array
• Number of Ways to Separate Numbers String, Suffix Array, Prefix Sum
• Painting a Grid With Three Different Colors Bitmask
• Minimum Incompatibility Array, Bit Manipulation, Bitmask
• Number of Distinct Roll Sequences Memoization
• Form Largest Integer With Digits That Add up to Target Array, String
• Build Array Where You Can Find The Maximum Exactly K Comparisons Prefix Sum
• Stone Game VIII Array, Math, Prefix Sum
• Allocate Mailboxes Array, Math, Sorting
• Constrained Subsequence Sum Array, Queue, Sliding Window
• Restore the Array String
• Count All Valid Pickup and Delivery Options Math, Combinatorics
• Maximum Height by Stacking Cuboids Array, Sorting
• Cherry Pickup II Array, Matrix
• Strange Printer String
• Number of Ways to Stay in the Same Place After Some Steps
• Maximum Value of K Coins From Piles Array, Prefix Sum
• Count Special Integers Math, Combinatorics
• Number of Great Partitions Array
• Minimum Cost to Split an Array Array, Hash Table, Counting
• Paths in Matrix Whose Sum Is Divisible by K Array, Matrix
• Count Different Palindromic Subsequences String
• Valid Palindrome III String
• String Compression II String
• Number of Increasing Paths in a Grid Array, Matrix, Depth-First Search
• Number of Restricted Paths From First to Last Node Graph, Shortest Path, Heap (Priority Queue)
• Minimum Moves to Spread Stones Over Grid Array, Matrix, Breadth-First Search
• Longest Increasing Path in a Matrix Array, Matrix, Depth-First Search
• Maximal Rectangle Array, Matrix, Stack
• Minimum Difficulty of a Job Schedule Array
• Minimum Cost to Cut a Stick Array, Sorting
• Minimum White Tiles After Covering With Carpets String, Prefix Sum
• Number of Ways to Earn Points Array
• Scramble String String
• Number of Music Playlists Math, Combinatorics
• Profitable Schemes Array
• Distinct Subsequences II String
• Cherry Pickup Array, Matrix
• Number of Ways to Paint N × 3 Grid
• Tallest Billboard Array
• Best Time to Buy and Sell Stock IV Array
• Burst Balloons Array
• Frog Jump Array, Hash Table
• Minimum Falling Path Sum II Array, Matrix
• Dungeon Game Array, Matrix
• Minimum Number of Refueling Stops Array, Greedy, Heap
• Minimum Number of Taps to Open to Water a Garden Array, Greedy, Intervals
• Russian Doll Envelopes Array, Binary Search, Sorting
• Split Array Largest Sum Array, Binary Search, Greedy
• Minimum Number of Flips to Make the Binary String Alternating String, Sliding Window, Greedy
• Minimum Window Subsequence String, Two Pointers, Sliding Window
• Count the Number of Square-Free Subsets Bit Manipulation, Bitmask, Math
• Maximum AND Sum of Array Bit Manipulation, Bitmask
• Minimum One Bit Operations to Make Integers Zero Bit Manipulation, Math
• Largest Multiple of Three Array, Greedy, Math
• Stone Game IV Math, Game Theory
• Stone Game III Array, Game Theory
• Palindrome Partitioning II String
• Wildcard Matching String, Greedy
• Distinct Subsequences String
• Max Dot Product Between Two Subsequences Array
• Minimum Insertion Steps to Make a String Palindrome String
• Longest Valid Parentheses String, Stack
• Count Vowels Permutation
• Best Time to Buy and Sell Stock III Array
• Regular Expression Matching String, Recursion
• Trapping Rain Water Array, Two Pointers, Stack

Companies that ask dynamic programming problems

• Amazon 166 problems on dynamic programming
• Google 155 problems on dynamic programming
• Microsoft 47 problems on dynamic programming
• Meta 32 problems on dynamic programming
• Adobe 29 problems on dynamic programming
• Uber 19 problems on dynamic programming
• Bloomberg 10 problems on dynamic programming
• Flipkart 7 problems on dynamic programming
• Apple 3 problems on dynamic programming
• Goldman Sachs 3 problems on dynamic programming
• Zoho 3 problems on dynamic programming
• TCS 2 problems on dynamic programming

Other topics

• Arrays 667 problems
• Strings 282 problems
• Math 213 problems
• Hash Table 202 problems
• Greedy 163 problems
• Sorting 156 problems
• Two Pointers 113 problems
• Matrix 107 problems
• Binary Search 95 problems
• Simulation 88 problems
• Bit Manipulation 83 problems
• Sliding Window 71 problems