53 dynamic programming interview questions [easy, medium, hard]

To ace your coding interview for a software engineering job, you’ll need to understand dynamic programming. Dynamic programming optimizes naive solutions to complex problems that have repeated recursive calls for the same inputs. This is achieved by storing solutions to simpler sub-problems to be used later so that they don’t need to be recalculated.

Let’s take a look at some typical dynamic programming questions.

6 typical dynamic programming interview questions

  • You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the fewest number of coins that you need to make up that amount.

  • You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

  • Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

  • Given n, calculate the Fibonacci sequence.

  • Given an m x n binary matrix filled with 0s and 1s, find the largest square containing only 1s and return its area.

  • Given an input string s and a pattern p, implement regular expression matching.

Below, we take a look at 50 dynamic programming questions and provide you with links to high quality solutions to them. 

This is an overview of what we’ll cover:

  1. Easy dynamic programming interview questions
  2. Medium dynamic programming interview questions
  3. Hard dynamic programming interview questions
  4. How to prepare for a coding interview

Let's get started.

1. Easy dynamic programming interview questions

You might be tempted to try to read all of the possible questions and memorize the solutions, but this is not feasible. Interviewers will always try to find new questions, or ones that are not available online. Instead, you should use these questions to practice the fundamental concepts of dynamic programming.

As you consider each question, try to replicate the conditions you’ll encounter in your interview. Begin by writing your own solution without external resources in a fixed amount of time.

If you get stuck, go ahead and look at the solution, but then try the next one alone again. Don’t get stuck in a loop of reading as many solutions as possible! We’ve analysed dozens of questions and selected ones that are commonly asked and have clear and high quality answers.

Here are some of the easiest questions you might get asked in a coding interview. These questions are often asked during the “phone screen” stage, so you should be comfortable answering them without being able to write code or use a whiteboard.

Question 1: Maximum subarray
Question 2: Climbing stairs
Question 3: Pascal's triangle
Question 4: Pascal's triangle II
Question 5: Best time to buy and sell stock
Question 6: Counting bits
Question 7: Is subsequence
Question 8: Fibonacci number
Question 9: Min cost climbing stairs
Question 10: Divisor game
Question 11: N-th tribonacci number
Question 12: Get maximum in generated array

2. Medium dynamic programming interview questions

Here are some moderate-level questions that are often asked in a video call or onsite interview. You should be prepared to write code or sketch out the solutions on a whiteboard if asked.

Question 13: Longest palindromic substring
Question 14: Unique paths
Question 15: Unique paths II
Question 16: Minimum path sum
Question 17: Decode ways
Question 18: Triangle
Question 19: Unique binary search trees
Question 20: Best time to buy and sell stock II
Question 21: Unique binary search trees II
Question 22: Interleaving string
Question 23: Palindrome partitioning
Question 24: Maximal square
Question 25: House robber
Question 26: Word break
Question 27: House robber II
Question 28: Maximum product subarray
Question 29: Longest increasing subsequence
Question 30: Perfect squares
Question 31: Partition equal subset sum
Question 32: Coin change

3. Hard dynamic programming interview questions

Similar to the medium section, these more difficult questions may be asked in an onsite or video call interview. You will likely be given more time if you are expected to create a full solution.

Question 33: Regular expression matching
Question 34: Maximal rectangle
Question 35: Edit distance
Question 36: Wildcard matching
Question 37: Distinct subsequences
Question 38: Palindrome partitioning II
Question 39: Scramble string
Question 40: Best time to buy and sell stock III
Question 41: Burst balloons
Question 42: Best time to buy and sell stock IV
Question 43: Dungeon game
Question 44: Frog jump
Question 45: Arithmetic slices II - subsequence
Question 46: Russian doll envelopes
Question 47: Freedom trail
Question 48: Cherry pickup
Question 49: Concatenated words
Question 50: Remove boxes
Question 51: Student attendance record II
Question 52: K inverse pairs array
Question 53: Decode ways II

4. How to prepare for a coding interview

4.1 Refresh your knowledge

Before you start practicing interviews,you’ll want to make sure you have a strong understanding of not only dynamic programming but also the rest of the relevant algorithms and data structures. Check out our guides for detailed explanations and useful cheat sheets.

Algorithms explained:

Data structure guides:

4.2 Practice on your own

Once you’re confident in all of these, you’ll want to start working through lots of coding problems.

For depth-first search you can obviously use the questions we’ve listed above. For the other algorithms you need to know, check out the rest of this series:

We also recommend working through our list of 73 data structure interview questions. To get used to an interview situation, where you’ll have to code on a whiteboard, we recommend solving the problems on a piece of paper or google doc. 

One of the main challenges of coding interviews is that you have to communicate what you are doing as you are doing it. Talking through your solution out loud is therefore very helpful. This may sound strange to do on your own, but it will significantly improve the way you communicate your answers during an interview. Of course, if it’s with someone else playing the role of the interviewer, even better.

4.3 Practice with others

However, sooner or later you’re probably going to want some expert interventions and feedback to really improve your coding interview skills.

That’s why we recommend practicing with ex-interviewers from top tech companies. If you know a software engineer who has experience running interviews at a big tech company, then that's fantastic. But for most of us, it's tough to find the right connections to make this happen. And it might also be difficult to practice multiple hours with that person unless you know them really well.

Here's the good news. We've already made the connections for you. We’ve created a coaching service where you can practice 1-on-1 with ex-interviewers from leading tech companies. Learn more and start scheduling sessions today.

cta_illustration arrow_left Browse FAANG ex-interviewers

Any questions about dynamic programming interview questions?

If you have any questions about dynamic programming or coding interviews in general, don't hesitate to ask them in the comments below. All questions are good questions, so go ahead!