6 Dynamic Programming problems for your next coding interview

Many programmers dread dynamic programming (DP) questions in their coding interviews. It’s easy to understand why. They’re hard!

For one, dynamic programming algorithms and patterns aren’t an easy concept to wrap your head around. Any expert developer will tell you that DP mastery involves lots of practice. It also requires an ability to break a problem down into multiple components, and combine them to get the solution.

Another part of the frustration also involves deciding whether or not to use DP to solve these problems. Most problems have more than one solution. How do you figure out the right approach? Memoization or recursion? Top-down or bottom-up?

So, we’ll unwrap some of the more common DP problems you’re likely to encounter in an interview, present a basic (or brute-force) solution, then offer one dynamic programming technique (written in Java) to solve each problem. You’ll be able to compare and contrast the approaches, to get a full understanding of the problem and learn the optimal solutions.

Examples in this article are in Java but you can also use Dynamic Programming in Python, JavaScript, C++, or other similar languages.

Master dynamic programming problems for coding interviews#

Confidently answer any dynamic programming question with expert strategies, patterns, and best practices.

Grokking Dynamic Programming Patterns for Coding Interviews

Given the weights and profits of N items, put these items in a knapsack which has a capacity C.

Your goal in the knapsack problem is: get the maximum profit from the items in the knapsack. Each item can only be selected once.

A common example of this optimization problem involves which fruits in the knapsack you’d include to get maximum profit.

Here’s the weight and profit of each fruit:

• Items: { Apple, Orange, Banana, Melon }
• Weight: { 2, 3, 1, 4 }
• Profit: { 4, 5, 3, 7 }
• Knapsack capacity: 5

Let’s try to put different combinations of fruits in the knapsack, such that their total weight is not more than 5.

• Apple + Orange (total weight 5) => 9 profit
• Apple + Banana (total weight 3) => 7 profit
• Orange + Banana (total weight 4) => 8 profit
• Banana + Melon (total weight 5) => 10 profit

This shows that Banana + Melon is the best combination, as it gives us the maximum profit and the total weight does not exceed the capacity. This practice in maximum sum planning is also useful to know for the System Design interview because it deals with programming a machine’s overall throughput to become as optimized as possible.

The problem#

Given two integer arrays to represent weights and profits of N items, find a subset of these items that will give us maximum profit such that their cumulative weight is not more than a given number C. Each item can only be selected once, so either you put an item in the knapsack or not.

The simple solution#

A basic brute force solution could be to try all combinations of the given items (as we did above), allowing us to choose the one with maximum profit and a weight that doesn’t exceed C. Take the example with four items (A, B, C, and D). To try all the combinations, the algorithm would look like:

For each item i create a new set which includes item i if the total weight does not exceed the capacity, and recursively process the remaining items. Create a new set without item i, and recursively process the remaining items return the set from the above two sets with higher profit

The Big O time complexity of the above algorithm is exponential $O(2^n)$, where n represents the total number of items. This is also shown from the above recursion tree. We have a total of 31 recursive calls, calculated through $(2^n) + (2^n)-1$, which is asymptotically equivalent to $O(2^n)$.

The space complexity is $O(n)$. This space is used to store the recursion stack. Since our recursive algorithm works in a depth-first fashion, we can’t have more than n recursive calls on the call stack at any time.

One dynamic programming solution: Top-down with memoization#

We can use an approach called memoization to overcome the overlapping sub-problems. Memoization is when we store the results of all the previously solved sub-problems and return the results from memory if we encounter a problem that’s already been solved.

Since we have two changing values (capacity and currentIndex) in our recursive function knapsackRecursive(), we can use a two-dimensional array to store the results of all the solved sub-problems. You’ll need to store results for every sub-array (i.e. for every possible index i) and for every possible capacity c.

Here’s the code:

What is the time and space complexity of the above solution? Since our memoization array $dp[profits.length][capacity+1]$ stores the results for all the subproblems, we can conclude that we will not have more than N*C subproblems (where $N$ is the number of items and $C$ is the knapsack capacity). This means that our time complexity will be $O(N*C)$.

The above algorithm will be using $O(N*C)$ space for the memoization array. Other than that we will use $O(N)$ space for the recursion call-stack. So the total space complexity will be $O(N*C + N)$, which is asymptotically equivalent to $O(N*C)$.

Given the weights and profits of N items, put these items in a knapsack with a capacity C. Your goal: get the maximum profit from the items in the knapsack. The only difference between the 0/1 Knapsack problem and this problem is that we are allowed to use an unlimited quantity of an item.

Using the example from the last problem, here are the weights and profits of the fruits:

• Items: { Apple, Orange, Melon }
• Weight: { 1, 2, 3 }
• Profit: { 15, 20, 50 }
• Knapsack capacity: 5

Try different combinations of fruits in the knapsack, such that their total weight is not more than 5.

• 5 Apples (total weight 5) => 75 profit
• 1 Apple + 2 Oranges (total weight 5) => 55 profit
• 2 Apples + 1 Melon (total weight 5) => 80 profit
• 1 Orange + 1 Melon (total weight 5) => 70 profit

2 apples + 1 melon is the best combination, as it gives us the maximum profit and the total weight does not exceed the capacity.

The problem#

Given two integer arrays representing weights and profits of N items, find a subset of these items that will give us maximum profit such that their cumulative weight is not more than a given number C. You can assume an infinite supply of item quantities, so each item can be selected multiple times.

The brute force solution#

A basic brute force solution could be to try all combinations of the given items to choose the one with maximum profit and a weight that doesn’t exceed C. Here’s what our algorithm will look like:

for each item i

• Create a new set which includes one quantity of item i if it does not exceed the capacity, and

• Recursively call to process all items

• Create a new set without item ‘i’, and recursively process the remaining items

Return the set from the above two sets with higher profit

The only difference between the 0/1 Knapsack optimization problem and this one is that, after including the item, we recursively call to process all the items (including the current item). In 0/1 Knapsack, we recursively call to process the remaining items.

Here’s the code:

The time and space complexity of the above algorithm is exponential $O(2^n)$, where $n$ represents the total number of items.

There’s a better solution!

One dynamic programming solution: Bottom-up programming#

Let’s populate our dp[][] array from the above solution, working in a bottom-up fashion. We want to “find the maximum profit for every sub-array and for every possible capacity”.

For every possible capacity c (i.e., 0 <= c <= capacity), there are two options:

1. Exclude the item. We will take whatever profit we get from the sub-array excluding this item: $dp[index-1][c]$
2. Include the item if its weight is not more than the c. We’ll include its profit plus whatever profit we get from the remaining capacity: $profit[index] + dp[index][c-weight[index]]$
3. Take the maximum of the above two values:

$*dp[index][c] = max (dp[index-1][c], profit[index] + dp[index][c-weight[index]])$

The problem#

Given a sequence, find the length of its Longest Palindromic Subsequence (or LPS). In a palindromic subsequence, elements read the same backward and forward.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: abdbca

Output: 5

Explanation: LPS is “abdba”.

Example 2:

Input: cddpd

Output: 3

Explanation: LPS is “ddd”.

Example 3:

Input: pqr

Output: 1

Explanation: LPS could be “p”, “q” or “r”.

The simple solution#

A basic brute-force solution could be to try all the subsequences of the given sequence. We can start processing from the beginning and the end of the sequence. So at any step, there are two options:

1. If the element at the beginning and the end are the same, we increment our count by two and make a recursive call for the remaining sequence.
2. We can skip the element either from the beginning or the end to make two recursive calls for the remaining subsequence. If option one applies, it will give us the length of LPS. Otherwise, the length of LPS will be the maximum number returned by the two recurse calls from the second option.

Here’s the code:

One dynamic programming solution: Top-down with memoization#

We can use an array to store the already solved subproblems.

The two changing values to our recursive function are the two indexes, startIndex and endIndex. We can then store the results of all the subproblems in a two-dimensional array.

Here’s the code:

The problem#

Write a function to calculate the nth Fibonacci number.

Fibonacci numbers are a series of numbers in which each number is the sum of the two preceding numbers. The first few Fibonacci numbers are 0, 1, 2, 3, 5, 8, and so on.

We can define the Fibonacci numbers as:

$Fib(n) = Fib(n-1) + Fib(n-2)$

for n > 1

Given that: $Fib(0) = 0$, and $Fib(1) = 1$

The basic solution#

A basic solution could be to have a recursive implementation of the above mathematical formula.

Here’s the code:

One dynamic programming solution: Bottom-up#

Let’s try to populate our dp[] array from the above solution, working in a bottom-up fashion. Since every Fibonacci number is the sum of previous two numbers, we can use this fact to populate our array.

Here is the code for our bottom-up dynamic programming approach:

We can optimize the space used in our previous solution. We don’t need to store all the Fibonacci numbers up to n, since we only need two previous numbers to calculate the next Fibonacci number. We can now further improve our solution:

The above solution has time complexity of $O(n)$ but a constant space complexity of $O(1)$.

Keep the learning going.#

For more practice, including dozens more problems and solutions, try Educative’s beloved course on dynamic programming patterns.

You’ll get hands-on practice with the recursive brute-force and advanced DP methods of Memoization and Tabulation.

Grokking Dynamic Programming Patterns for Coding Interviews

The problem#

Given two strings s1 and s2, find the length of the longest substring common in both the strings.

Example 1:

Input: s1 = “abdca”

s2 = “cbda”

Output: 2

Explanation: The longest common substring is bd.

Example 2:

Input: s1 = “passport”

s2 = “ppsspt”

Output: 3

Explanation: The longest common substring is “ssp”.

The simple solution#

A basic brute-force solution could be to try all substrings of s1 and s2 to find the longest common one. We can start matching both the strings one character at a time, so we have two options at any step:

1. If the strings have a matching character, we can recursively match for the remaining lengths and keep track of the current matching length.
2. If the strings don’t match, we can start two new recursive calls by skipping one character separately from each string.

The length of the Longest common Substring (LCS) will be the maximum number returned by the three recurse calls in the above two options.

Here’s the code:

The time complexity of the above algorithm is exponential $O(2^(m+n))$, where $m$ and $n$ are the lengths of the two input strings. The space complexity is $O(n+m)$, this space will be used to store the recursion stack.

One dynamic programming solution: Top-down with memoization#

We can use an array to store the already solved subproblems.

The three changing values to our recursive function are the two indexes (i1 and i2) and the count. Therefore, we can store the results of all subproblems in a three-dimensional array. (Another alternative could be to use a hash-table whose key would be a string.

Here’s the code:

The problem#

Given two strings s1 and s2, find the length of the longest subsequence which is common in both the strings.

Example 1:

Input: s1 = “abdca”

s2 = “cbda”

Output: 3

Explanation: The longest substring is bda.

Example 2:

Input: s1 = “passport”

s2 = “ppsspt”

Output: 5

Explanation: The longest substring is psspt.

The simple solution#

A basic brute-force solution could be to try all subsequences of s1 and s2 to find the longest one. We can match both the strings one character at a time. So for every index i in s1 and j in s2 we must choose between:

1. If the character s1[i] matches s2[j], we can recursively match for the remaining lengths.
2. If the character s1[i] does not match s2[j], we will start two new recursive calls by skipping one character separately from each string.

Here’s the code:

One dynamic programming solution: Bottom-up#

Since we want to match all the subsequences of the given two strings, we can use a two-dimensional array to store our results. The lengths of the two strings will define the size of the array’s two dimensions. So for every index i in string s1 and j in string s2, we can choose one of these two options:

1. If the character s1[i] matches s2[j], the length of the common subsequence would be one, plus the length of the common subsequence till the i-1 and j-1 indexes in the two respective strings.
2. If the character s1[i] doesn’t match s2[j], we will take the longest subsequence by either skipping ith or jth character from the respective strings.

So our recursive formula would be:

if si[i] == s2[j]

dp[i][j] = 1 + dp[i-1][j-1]

else

dp[i][j] = max(dp[i-1)[j], dp[i][j-1])

Here’s the code:

The time and space complexity of the above algorithm is $O(m*n)$, where $m$ and $n$ are the lengths of the two input strings.

Missing Canon#

To round out Dynamic Programming (DP) coverage for your next coding interview, make sure you include short stubs (problem + state + recurrence) for these essential patterns:

Edit Distance (Levenshtein)#

dp[i][j] = min edits to convert s1[0..i) → s2[0..j)
Transitions: insert, delete, replace.

Coin Change (minimum coins)#

dp[c] = min coins to make amount c
Transition: iterate over coin values; handle “no solution.”

Coin Change (number of ways)#

dp[i][c] = ways to make c using first i coins
Careful with iteration order to avoid double counting.

Longest Increasing Subsequence#

O(n²) DP on dp[i] = LIS ending at i, or O(n log n) using patience sorting.
Excellent follow-up question in interviews.

Partition Equal Subset Sum#

Boolean knapsack: dp[c] true/false to determine if a subset sums to total/2.

Unique Paths / Minimum Path Sum (grid)#

dp[i][j] depends on top/left neighbors; great introductory grid DP examples.

House Robber / Circular Robber#

dp[i] = best value up to i with take/skip transitions; circular version splits into two runs.

Decode Ways#

dp[i] = ways to decode prefix 0..i;
handle edge cases with zeros and valid 10–26 mappings.

Rod Cutting#

Profit maximization version of unbounded knapsack.

Even brief outlines for each of these “canonical” problems make your notes or guide a complete one-stop DP reference.

Keep learning dynamic programming problems!#

This is just a small sample of the dynamic programming problems and concepts and problems you may encounter in coding interview questions.

Some more dynamic programming problems, data structures, and algorithms:

• Binary trees

• The coin change problem

• Modified binary search

• Greedy algorithms

• Backtracking

• Minimum cost problems

• Subsequence problems

• Palindrome partitioning

For more of this practice, including dozens more problems and solutions for each pattern, check out Educative’s beloved course Grokking Dynamic Programming Patterns for Coding Interviews. In each pattern, we’ll start with a recursive brute-force solution. Once we have a recursive solution, we’ll then apply the advanced DP methods of Memoization and Tabulation.

The practice problems in this course were carefully chosen, covering the most frequently asked dynamic programming problems in coding interviews with a variety of relevant programming languages.

How to Present DP Answers in Interviews#

A clear structure is as important as the solution itself. Use this checklist to sound confident and organized when explaining any Dynamic Programming (DP) problem in an interview.

State#

Start with one crisp sentence:
“Let dp[i][j] be …” (define exactly what the state represents).

Base#

List all trivial or boundary cases explicitly.
Examples: dp[0] = 0, dp[i][0] = 1, or “if string is empty, return 0.”

Recurrence#

Write the formula and explain the choices:
take / skip, match / mismatch, include / exclude.
Show how the recurrence follows from subproblems.

Order & Complexity#

Name the loop order (e.g., increasing i, decreasing c).
State both time and space complexity.
Mention any space optimizations (rolling arrays, 1-D compression).

Reconstruction#

Describe how you’d rebuild the answer:
use parent pointers, backtracking, or a reverse walk through the DP table.

Edge cases#

Always consider:

• Empty input
• All negatives or zeros
• Ties in max/min
• Large capacities or long strings
• Zeros in decoding or coin sets

Pro tip#

Stick to this script — it’s concise, complete, and systematic.
That’s exactly how top candidates handle Dynamic Programming problems in coding interviews.

Good luck, and happy learning!

Continue reading about coding interviews and dynamic programming problems#

• Dynamic Programming Tutorial: making efficient programs in Python
• The Coding Interview FAQ: preparation, evaluation, and structure
• Acing the JavaScript Interview: top questions explained