Dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems, solving each of those subproblems just once, and storing their solutions using a memory-based data structure (array, map, etc). Each of the subproblem solutions is indexed in some way, typically based on the values of its input parameters, so as to facilitate its lookup. So, the next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time. This technique of storing solutions to subproblems instead of recomputing them is called memoization.

Here is a brilliant explanation given on Quora to explain the concept of dynamic programming to a kid.

**writes down “1+1+1+1+1+1+1+1 =” on a sheet of paper**

“What’s that equal to?”

*counting* “Eight!”

*writes down another “1+” on the left*

“What about that?”

*quickly* “Nine!”

“How’d you know it was nine so fast?”

“You just added one more”

“So you didn’t need to recount because you remembered there were eight! Dynamic Programming is just a fancy way to say ‘remembering stuff to save time later'”

“What’s that equal to?”

*counting* “Eight!”

*writes down another “1+” on the left*

“What about that?”

*quickly* “Nine!”

“How’d you know it was nine so fast?”

“You just added one more”

“So you didn’t need to recount because you remembered there were eight! Dynamic Programming is just a fancy way to say ‘remembering stuff to save time later'”

In this post, we have listed out commonly asked interview questions that can be solved using dynamic programming:

- Introduction to Dynamic ProgrammingBeginner
- Longest Common Subsequence ProblemMedium
- Longest Common Subsequence (LCS) | Space optimized versionMedium
- Longest Common Subsequence of k–sequencesMedium
- Longest Common Subsequence | Finding all LCSHard
- Longest Common Substring ProblemMedium
- Longest Palindromic Subsequence using Dynamic ProgrammingMedium
- Longest Repeated Subsequence ProblemMedium
- Implement Diff UtilityMedium
- Shortest Common Supersequence ProblemMedium
- Shortest Common Supersequence | Finding all SCSHard
- Shortest Common Supersequence Problem using LCSHard
- Longest Increasing Subsequence using Dynamic ProgrammingHard
- Longest Decreasing Subsequence ProblemHard
- Longest Bitonic SubsequenceMedium
- Maximum Sum Increasing Subsequence ProblemMedium
- The Levenshtein distance (Edit distance) ProblemMedium
- Find the size of the largest square submatrix of 1’s present in a binary matrixMedium
- Matrix Chain Multiplication using Dynamic ProgrammingHard
- Find minimum cost to reach the last cell of a matrix from its first cellMedium
- Find the longest sequence formed by adjacent numbers in the matrixMedium
- Count the number of paths in a matrix with a given cost to reach the destination cellMedium
- 0–1 Knapsack ProblemMedium
- Maximize the value of an expressionHard
- Partition Problem using Dynamic ProgrammingMedium
- Subset Sum Problem – Dynamic Programming SolutionMedium
- 3–Partition ProblemMedium
- Minimum Sum Partition ProblemHard
- Rod Cutting ProblemMedium
- Maximum Product Rod CuttingMedium
- Coin change-making problemMedium
- Coin Change ProblemHard
- Total possible solutions to a linear equation of
`k`

variablesHard - Longest Alternating Subsequence ProblemMedium
- Count the number of times a pattern appears in a given string as a subsequenceHard
- Collect maximum points in a matrix by satisfying given constraintsHard
- Find all N-digit binary strings without any consecutive 1’sEasy
- Count total possible combinations of n-digit numbers in a mobile keypadMedium
- Word Break Problem – Dynamic ProgrammingHard
- Determine the minimal adjustment cost of an arrayHard
- Check if a string is k–palindrome or notHard
- Find total ways to achieve a given sum with
`n`

throws of dice having`k`

facesMedium - Wildcard Pattern MatchingHard
- Find the number of ways to fill an
`N × 4`

matrix with`1 × 4`

tilesMedium - Ways to reach the bottom-right corner of a matrix with exactly
`k`

turns allowedHard - Weighted Interval Scheduling ProblemMedium
- Box Stacking ProblemHard
- Find total ways to reach n’th stair with at-most
`m`

stepsMedium - Find total ways to reach the n’th stair from the bottomMedium
- Activity Selection Problem using Dynamic ProgrammingMedium
- Find the minimum number of deletions required to convert a string into a palindromeMedium
- Calculate the minimum cost to reach the destination city from the source cityMedium
- Pots of Gold Game Problem using Dynamic ProgrammingHard
- Find minimum cuts needed for the palindromic partition of a stringHard
- Weighted Interval Scheduling – Dynamic Programming SolutionMedium
- Find minimum jumps required to reach the destinationMedium
- Find the probability that a person is alive after taking
`n`

steps on an islandMedium - Maximum Length Snake SequenceMedium
- Calculate the size of the largest plus of 1’s in a binary matrixHard
- Longest Increasing Subsequence using LCSMedium
- Find maximum profit earned from at most
`k`

stock transactionsHard - Count all paths in a matrix from the first cell to the last cellEasy
- Check if a string matches with the given wildcard patternHard
- Check if a string is interleaving of two other given stringsMedium
- Find all employees who directly or indirectly reports to a managerHard
- Find optimal cost to construct a binary search treeHard
- Find the maximum sum of a subsequence with no adjacent elementsMedium
- Minimum-weight triangulation of a convex polygonHard
- Find maximum profit that can be earned by conditionally selling stocksEasy
- Program to find n’th Fibonacci numberEasy
- Count decodings of a given sequence of digitsMedium
- Hat Check Problem – Counting DerangementsMedium
- Maximum Independent Set ProblemMedium
- Find the minimum number of squares that sum to a given numberMedium
- Truncate an integer array such that
`2×min`

becomes more than`max`

Hard - Maximum Sum Subarray Problem (Kadane’s Algorithm)Easy
- Longest Alternating Subarray ProblemEasy
- Find maximum profit earned from at most two stock transactionsHard
- Find ways to calculate a target from elements of the specified arrayMedium
- Calculate the sum of all elements in a submatrix in constant timeMedium
- Find maximum sum
`K × K`

submatrix in a given`M × N`

matrixHard - Find maximum sum submatrix present in a matrixMedium
- Find the length of the longest path in a matrix with consecutive charactersMedium
- Collect maximum value of coins in a matrixHard
- Single-Source Shortest Paths – Bellman–Ford AlgorithmMedium
- All-Pairs Shortest Paths – Floyd Warshall AlgorithmEasy
- Determine a negative-weight cycle in a graphMedium
- Word Break Problem – Using Trie Data StructureMedium

**Thanks for reading.**

To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.

**Like us? Refer us to your friends and support our growth. Happy coding** :)