7 steps of solving Dynamic Programming Problems?

The key to solving Dynamic programming problems is first identifying them. It’s very similar to recursive problems like those binary tree problems and linked list-based problems we have solved before. You first see if the whole problem can be broken down into smaller problems.

For example in the climbing stairs problem, you can break down the n step problem into 1 step or 2 step problems.

Once you can do that, you see if the complete solution can be obtained by combining the solution of subproblems, that’s the key. If this holds true then its most likely Dynamic programming problems and you can use the divide and conquer, Recursion, and Memoization to solve the problems. Here are the 7 steps of solving dynamic programming (DP) basic doing problems

Recognize a DP problem by breaking it down into subproblems
Identify problem variables.
Clearly express the recurrence relation to applying recursion.
Identify the base cases.
Decide if you want to implement it iteratively or recursively.
Add memoization.
Determine time complexity.

You can also use the FAST method to solve dynamic programming problems which is an acronym for the 4 steps you need to solve any dynamic programming problem:

Find the First Solution
Analyze the First Solution
Identify the Subproblems
Turn around the solution

You can use these techniques to identify and solve the Dynamic Programming problem. I also highly recommend the Master the art of Dynamic Programming course on Udemy to try a couple of guided problems to understand how these steps fit together, particularly if you have never solved a Dynamic Programming problem.

If you need a book, I highly recommend Grokking Algorithms book by Aditya Bhargava which also explains Knapsack’s problem in good detail and teaches you how to solve Dynamic programming problems.

20 Dynamic Programming Coding Problems for Programming and Tech interviews

Without wasting any more of your time, here is a list of the most popular and frequently asked Dynamic programming-based coding problems from interviews.

They are not only great to practice this difficult technique but also gives you an opportunity to test your DP problem-solving skills.

If you can solve 5 out of these 10 questions without any help, you are in a good place to attempt coding interviews.

1. The Climbing Stairs problem

This is one of the most popular coding problems which can be solved using the Dynamic Programming technique. In this problem, you are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. The question is, in how many distinct ways can you climb to the top? Note: Given n will be a positive integer. Example 1: Input: 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps

Example 2: Input: 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step.

If you get stuck then you can also watch this video to get some idea and if you need a course, Master the Coding Interview: Big Tech (FAANG) Interviews by Andrei Negaoie is the best course where you will not only find the solution of this problem but many others like this one.

2. The Knapsack problem [Solved]

This is another common Dynamic programming-based coding problem and a pattern which can solve many such questions. In this type of problem, you will be given the weights and profits of ’N’ items, put these items in a knapsack which has a capacity ‘C’. Your goal: 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 getting 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. You can also see this free lesson from the Dynamic Programming course on Educative for a detailed solution to this problem.

3. Edit Distance Problem

This is one of the easier dynamic programming problems. In this question, you will be given two words word1 and word2, to find the minimum number of operations required to convert word1 to word2. You have the following 3 operations permitted on a word:

Insert a character
Delete a character
Replace a character

Example 1: Input: word1 = “horse”, word2 = “ros” Output: 3 Explanation: horse -> rorse (replace ‘h’ with ‘r’) rorse -> rose (remove ‘r’) rose -> ros (remove ‘e’)

And, if you get stuck, watch this YouTube tutorial to get unstuck and for step by step solution:

4. Longest palindromic subsequence Question

This is another common Dynamic programming question and pattern. In this type of DP question, you will be 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: “bbbab”

Output: 4

Explanation: LPS is “bbbb”.

And, if you need solution, watch this video tutorial on YouTube, its free and provide step by step solution for this Dynamic Programming problem.

4. Best Time to Buy and Sell Stock Problem

This is one of the hard Dynamic programming problems which need some experience to solve. In this question, you will be given an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1: Input: [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6–1 = 5. Not 7–1 = 6, as the selling price needs to be larger than buying price. You can try this problem on your own but if you stuck you can also see the solution here on Educative.

5. The Fibonacci problem [Solution]

This is one of the easiest dynamic programming questions and many of you have already solved it without even knowing that you are using Dynamic programming. This is also the most common example of DP and many instructors use Fibonacci numbers to teach Dynamic programming. In this question, you will be asked to 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 You can also see my solution of how to calculate the Nth Fibonacci number in Java to learn more about how to solve this problem.

6. The Coin Change Problem

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up of any combination of the coins, return -1.

Example 1: Input: coins = [1, 2, 5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1

And, if you stuck, here is the tutorial to get help

7. Longest common substring

Given two strings 1’ 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”.

And, here is the solution of Longest Common Substring problem:

8. Longest common subsequence

Given two strings 1’ 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”.

And, if you get stuck then you can always watch this video on YouTube to get ideas about how to solve this Dynamic Programming question:

9. Equal Subset Sum Partition Problem

This is another popular Dynamic Programming question that is very similar to the Knapsack problem. If you know how to solve knapsack then you can solve this too.

In his problem you are given a set of positive numbers, find if we can partition it into two subsets such that the sum of elements in both the subsets is equal.

Example 1:

Input: {1, 2, 3, 4}

Output: True

Explanation: The given set can be partitioned into two subsets with equal sum: {1, 4} & {2, 3}

Example 2:

Input: {1, 1, 3, 4, 7}

Output: True

Explanation: The given set can be partitioned into two subsets with equal sum: {1, 3, 4} & {1, 7}

Example 3:

Input: {2, 3, 4, 6}

Output: False

Explanation: The given set cannot be partitioned into two subsets with an equal sum.

You can try solving the problem on your own but if you stuck then you can also see the solution here on Educative. This free lesson is part of their Dynamic Programming course which explains this problem in detail and also shows you how to solve it in your browser.

10. Continuous Subarray Sum

This is another popular dynamic programming-based coding problem from interviews. In this problem, you will be given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to a multiple of k, that is, sums up to n*k where n is also an integer.

Example 1: Input: [23, 2, 4, 6, 7], k=6

Output: True Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

And, if you get stuck, you can watch this video to get ideas about how to solve this DP problem but I suggest first try yourself

10 More Dynamic Programming Interview Qustions for Practice

And here are 10 more Dynamic Programming Interview questions you can practice

Word Break Problem
Maximal Product when Cutting Rope
Dice Throw Problem
Box Stacking
Egg Dropping Puzzle
Boolean Parenthesization Problem
Shortest Common Supersequence
Matrix Chain Multiplication
Partition problem
Unique Paths

That’s all about some of the frequently asked Dynamic Programming problems from Interviews. Btw, this is just a small sample of the dynamic programming concepts and problems you may encounter in a coding interview.

Solving these problems will give you enough idea about how to identify Dynamic programming problems during coding interviews as well as how to solve them in a limited time.

These questions also cover all essential Dynamic programming patterns like the Knapsack problem which can be used to solve a host of DP problems.

Some Useful Resources for Coding Interviews:

Thanks for reading this article so far. If you like these Dynamic Programming problems and interview questions then please share them with your friends and colleagues. If you have any questions or feedback then please drop a note.

P. S. — If you need more practice, including dozens more problems and solutions for each pattern, check out Grokking Dynamic Programming Patterns for Coding Interviews on Educative. It’s an excellent, text-based interactive course to build your Dynamic programming skills.

Educative as a platform is also a great resource for coding interviews and you can get all of their course access by just $14.9 per month. I highly recommend this to anyone preparing for programming job interviews.

Top 20 Dynamic Programming Interview Questions for Software Engineers

Preparing for Coding interview? Here are 20 Dynamic Programming problems to test your skills and prepare well.