Skip to main content

Essential Dynamic Programming Problems for SDE Interviews

· 10 min read

If you're gearing up for placement season or trying to finally conquer DP (we've all been there!), I've compiled a list of hand-picked problems that cover the depth and breadth of dynamic programming.

Connect with me on LinkedIn to stay updated with more coding resources, interview tips, and problem-solving strategies!

This isn't a guaranteed ticket to ace every DP question. DP is hard, arguably the hardest topic in DSA interviews. But these are the standard problems and patterns that keep showing up in actual interviews, coding assessments, and company hiring tests.

I've organized these by pattern types because that's how your brain will work during interviews. You won't think "ah, this is LeetCode #123." You'll think "this looks like a path-counting problem" or "this feels like interval DP."

Not too many problems to overwhelm you. Not too few to leave gaps. Just the focused set you need to build that DP intuition.

Let's crack DP together!

Problem List by Pattern​

1. 1D DP - Fundamentals​

  1. Climbing Stairs
  2. Min Cost Climbing Stairs
  3. House Robber
  4. House Robber II
  5. Maximum Product Subarray
  6. Longest Increasing Subsequence
  7. Jump Game
  8. Jump Game II
  9. Decode Ways
  10. Coin Change
  11. Coin Change 2
  12. Perfect Squares
  13. Partition Equal Subset Sum
  14. Dice Roll Simulation
  15. Removing Digits

2. 2D DP - Grid & Matrix Problems​

  1. Unique Paths
  2. Unique Paths II
  3. Minimum Path Sum
  4. Maximum Square
  5. Dungeon Game
  6. Triangle
  7. Minimum Falling Path Sum
  8. Cherry Pickup
  9. Cherry Pickup II
  10. Grid Paths

3. Knapsack Problems (0/1, Unbounded, Variants)​

  1. Target Sum
  2. Last Stone Weight II
  3. Ones and Zeroes
  4. Combination Sum IV
  5. Profitable Schemes
  6. Tallest Billboard
  7. Book Shop
  8. Array Description

4. Longest Common Subsequence (LCS) Variants​

  1. Longest Common Subsequence
  2. Edit Distance
  3. Delete Operation for Two Strings
  4. Minimum ASCII Delete Sum for Two Strings
  5. Distinct Subsequences
  6. Shortest Common Supersequence
  7. Longest Palindromic Subsequence
  8. Minimum Insertion Steps to Make a String Palindrome
  9. Interleaving String
  10. Uncrossed Lines

5. Palindrome DP​

  1. Longest Palindromic Substring
  2. Palindromic Substrings
  3. Palindrome Partitioning II
  4. Palindrome Removal
  5. Count Different Palindromic Subsequences
  6. Longest Palindromic Subsequence II

6. String DP (Beyond LCS)​

  1. Regular Expression Matching
  2. Wildcard Matching
  3. Scramble String
  4. Distinct Subsequences II
  5. Number of Ways to Form a Target String Given a Dictionary
  6. Edit Distance

7. Stock Problems (State Machine DP)​

  1. Best Time to Buy and Sell Stock
  2. Best Time to Buy and Sell Stock II
  3. Best Time to Buy and Sell Stock III
  4. Best Time to Buy and Sell Stock IV
  5. Best Time to Buy and Sell Stock with Cooldown
  6. Best Time to Buy and Sell Stock with Transaction Fee

8. DP on Trees​

  1. House Robber III
  2. Binary Tree Maximum Path Sum
  3. Unique Binary Search Trees
  4. Unique Binary Search Trees II
  5. Longest Univalue Path
  6. Binary Tree Cameras
  7. Tree Diameter
  8. Tree Distances I
  9. Tree Distances II

9. Interval DP​

  1. Minimum Cost Tree From Leaf Values
  2. Burst Balloons
  3. Remove Boxes
  4. Strange Printer
  5. Minimum Cost to Merge Stones
  6. Predict the Winner
  7. Stone Game
  8. Stone Game II

10. Digit DP​

  1. Count Numbers with Unique Digits
  2. Non-negative Integers without Consecutive Ones
  3. Numbers At Most N Given Digit Set
  4. Numbers With Repeated Digits
  5. Count Special Integers

11. Bitmask DP​

  1. Partition to K Equal Sum Subsets
  2. Shortest Path Visiting All Nodes
  3. Find the Shortest Superstring
  4. Number of Ways to Wear Different Hats to Each Other
  5. Minimum Cost to Connect Two Groups of Points
  6. Maximum Students Taking Exam
  7. Hamming Distance
  8. Elevator Rides

12. DP with Optimization Tricks​

  1. Maximal Rectangle
  2. Largest Rectangle in Histogram
  3. Russian Doll Envelopes
  4. Maximum Height by Stacking Cuboids
  5. Number of Longest Increasing Subsequence
  6. Longest Arithmetic Subsequence
  7. Longest Arithmetic Subsequence of Given Difference

13. Probability & Expected Value DP​

  1. Knight Probability in Chessboard
  2. Soup Servings
  3. New 21 Game
  4. Airplane Seat Assignment Probability

14. Game Theory DP​

  1. Divisor Game
  2. Stone Game III
  3. Stone Game IV
  4. Stone Game V
  5. Stone Game VI
  6. Stone Game VII
  7. Nim Game
  8. Can I Win

15. Advanced DP Patterns​

  1. Frog Jump
  2. Split Array Largest Sum
  3. Count of Range Sum
  4. Freedom Trail
  5. Minimum Swaps To Make Sequences Increasing
  6. Paint House III
  7. Number of Music Playlists
  8. Number of Ways to Reorder Array to Get Same BST
  9. Count All Valid Pickup and Delivery Options
  10. Constrained Subsequence Sum

16. Competitive Programming DP Classics​

  1. Dice Combinations
  2. Minimizing Coins
  3. Coin Combinations I
  4. Coin Combinations II
  5. Two Sets II
  6. Rectangle Cutting
  7. Money Sums
  8. Counting Towers
  9. Projects
  10. Increasing Subsequence
  11. ABC 129 C - Typical Stairs
  12. ABC 153 E - Crested Ibis vs Monster
  13. ABC 167 E - Colorful Blocks
  14. ABC 179 D - Leaping Tak
  15. ABC 184 E - Third Avenue
  16. Educational DP Contest
  17. CF - Xenia and Ringroad
  18. CF - Mashmokh and ACM
  19. CF - R2D2 and Droid Army
  20. CF - Maximum Absurdity

Why This List Works​

Pattern-Based Organization: Each section focuses on a specific DP pattern, making it easier to build mental models and recognize similar problems during interviews.

Progressive Difficulty: Within each pattern, problems range from fundamental to advanced, allowing you to build confidence gradually.

Comprehensive Coverage: From 1D DP fundamentals to advanced bitmask DP and game theory, this list covers all major DP patterns you'll encounter in interviews.

Competitive Programming: The CSES, AtCoder, and Codeforces problems provide additional challenge and help you develop speed and accuracy under time constraints.

Final Thoughts​

Don't just memorize solutions. Understand the transitions. That's what separates those who "get" DP from those who struggle with it.

This list represents the most important DP problems you should solve before interviews. It's not about quantity, it's about building strong pattern recognition and problem-solving intuition.

DP is hard, but with focused practice on these patterns, you'll develop the intuition needed to tackle any DP problem in interviews.

Let's connect on LinkedIn - I regularly share interview tips, problem-solving strategies, and coding resources that can help accelerate your preparation!

You've got this!