Skip to main content

Pattern · 35 problems

Dynamic Programming Interview Problems

Dynamic programming is recursion that remembers. I define the state in one sentence, then ask what it depends on.

Get the link for your laptop

Free: write the code and run it, no sign-up.

When I reach for it

  • Brute force repeats the same subproblem.
  • You are asked for a count, a minimum or a maximum.
  • The answer for n builds on answers for smaller n.

Problems, easiest first

3 easy · 25 medium · 7 hard. Open one to read it, then write it in the free editor.

  1. Counting BitseasyBit Manipulation
  2. Climbing Stairseasy
  3. Min Cost Climbing StairseasyArrays & Hashing
  4. Decode WaysmediumStrings
  5. House RobbermediumArrays & Hashing
  6. House Robber IImediumArrays & Hashing
  7. Jump GamemediumGreedyArrays & Hashing
  8. Longest Common SubsequencemediumStrings
  9. Longest Increasing SubsequencemediumBinary SearchArrays & Hashing
  10. Longest Palindromic SubstringmediumTwo PointersStrings
  11. Maximum Product SubarraymediumArrays & Hashing
  12. Maximum SubarraymediumArrays & Hashing
  13. Non-overlapping IntervalsmediumIntervalsGreedy
  14. Palindromic SubstringsmediumTwo PointersStrings
  15. Unique Pathsmedium
  16. Coin ChangemediumBFS & DFSArrays & Hashing
  17. Word BreakmediumTreesStrings
  18. Cheapest Flights Within K StopsmediumHeapsGraphs
  19. Coin Change IImediumArrays & Hashing
  20. Edit DistancemediumStrings
  21. Equal Sum Array PartitionmediumArrays & Hashing
  22. Generate ParenthesesmediumBacktrackingStrings
  23. Interleaving StringmediumStrings
  24. Jump Game IImediumGreedyArrays & Hashing
  25. Palindrome PartitioningmediumBacktrackingStrings
Show the other 10 problems
  1. Stock Trading with CooldownmediumArrays & Hashing
  2. Target SummediumBacktrackingArrays & Hashing
  3. Valid Parenthesis StringmediumStackGreedy
  4. Binary Tree Maximum Path SumhardTreesBFS & DFS
  5. Burst BalloonshardArrays & Hashing
  6. Distinct SubsequenceshardStrings
  7. Longest Increasing Path in a MatrixhardGraphsBFS & DFS
  8. Regular Expression MatchinghardBacktrackingStrings
  9. Trapping Rain WaterhardStackHeaps
  10. Maximum Profit in Job SchedulinghardBinary SearchArrays & Hashing

The idea

Define the state in one sentence, such as: dp[i] is the best answer using the first i items. Then write how it depends on smaller states.

Start with plain recursion. Add a cache. Then, if you want, turn it into a table. Each step keeps the logic and cuts the cost.

INF = float("inf")
dp = [0] + [INF] * amount            # dp[a] = fewest coins to make a
for a in range(1, amount + 1):
    for coin in coins:
        if coin <= a:
            dp[a] = min(dp[a], dp[a - coin] + 1)
return dp[amount] if dp[amount] != INF else -1
Fewest coins for an amount. The state sentence is the comment on the first line. Python shown; the idea carries to every language in the editor.

Where it goes wrong

  • A vague state. If you cannot say it in one sentence, redo it.
  • Wrong or missing base cases.
  • Filling a table in the wrong order. Smaller states must come first.

Say this before you type. Say the state in one sentence, then say which smaller states it reads from.

Where Coco comes in

Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.

Questions people ask

Top-down or bottom-up?
Top-down is easier to get right, because it follows the recursion. Bottom-up avoids recursion limits and can shrink the memory.
How do I spot a dynamic programming problem?
Brute force repeats the same subproblems, and a greedy choice can fail. That pairing points to dynamic programming.

Meet these next

Fin and Coco are characters, not people. strongyes.io is independent. Leo builds it with AI agents.