A 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’s brilliant explanation given by Jonathan Paulson on Quora on 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'”

Below is the list of commonly asked interview questions that can be solved using Dynamic programming –

- Longest Common Subsequence | Introduction & LCS Length

- Longest Common Subsequence | Space optimized version

- Longest Common Subsequence of K-sequences

- Longest Common Subsequence | Finding all LCS

- Longest Common Substring problem

- Longest Palindromic Subsequence using Dynamic Programming

- Longest Repeated Subsequence problem

- Implement Diff Utility

- Shortest Common Supersequence | Introduction & SCS Length

- Shortest Common Supersequence | Finding all SCS

- Shortest Common Supersequence | Using LCS

- Longest Increasing Subsequence using Dynamic Programming

- Longest Bitonic Subsequence

- Increasing Subsequence with Maximum Sum

- Longest Decreasing Subsequence Problem

- The Levenshtein distance (Edit distance) problem

- Find size of largest square sub-matrix of 1’s present in given binary matrix

- Matrix Chain Multiplication

- Find the minimum cost to reach last cell of the matrix from its first cell

- Find longest sequence formed by adjacent numbers in the matrix

- Count number of paths in a matrix with given cost to reach destination cell

- 0-1 Knapsack problem

- Maximize value of the expression

- Partition problem

- Subset sum problem

- Minimum Sum Partition problem

- Find all N-digit binary strings without any consecutive 1’s

- Rod Cutting

- Maximum Product Rod Cutting

- Coin change-making problem (unlimited supply of coins)

- Coin Change Problem – Find total number of ways to get the denomination of coins

- Longest alternating subsequence

- Count number of times a pattern appears in given string as a subsequence

- Collect maximum points in a matrix by satisfying given constraints

- Count total possible combinations of N-digit numbers in a mobile keypad

- Find optimal cost to construct binary search tree

- Word Break Problem

- Word Break Problem | Using Trie Data Structure

- Total possible solutions to linear equation of k variables

- Wildcard Pattern Matching

- Find probability that a person is alive after taking N steps on the island

- Calculate sum of all elements in a sub-matrix in constant time

- Find maximum sum K x K sub-matrix in a given M x N matrix

- Find maximum sum submatrix present in a given matrix

- Find maximum sum of subsequence with no adjacent elements

- Maximum subarray problem (Kadane’s algorithm)

- Single-Source Shortest Paths – Bellman Ford Algorithm

- All-Pairs Shortest Paths – Floyd Warshall Algorithm

- Pots of Gold Game using Dynamic Programming

- Find minimum cuts needed for palindromic partition of a string

- Maximum Length Snake Sequence

- 3 Partition Problem

- Calculate size of the largest plus of 1’s in binary matrix

- Check if given string is interleaving of two other given strings

- Longest Increasing Subsequence using LCS

**Thank you for being with us. 🙂**

## Leave a Reply