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 on concept of Dynamic Programming on Quora Jonathan Paulson’s answer
to How should I explain dynamic programming to a 4-year-old?

Please find below top 50 common data structure problems that can be solved using Dynamic
programming -

Longest Common Subsequence | Introduction & LCS Length

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

Longest Increasing Subsequence using Dynamic Programming

Longest Bitonic Subsequence

Increasing Subsequence with Maximum Sum

The Levenshtein distance (Edit distance) problem

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

Matrix Chain Multiplication using Dynamic Programming

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 the Value of an Expression

Partition problem | Dynamic Programming Solution

Subset Sum Problem

Minimum Sum Partition Problem

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

Rod Cutting Problem

Maximum Product Rod Cutting

Coin change-making problem (unlimited supply of coins)

Coin Change Problem (Total number of ways to get the denomination of coins)

Longest Alternating Subsequence Problem

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 | Dynamic Programming

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 an Island

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

Find Maximum Sum Submatrix in a given 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

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 on concept of Dynamic

Programming on Quora Jonathan Paulson’s answer to How
should I explain dynamic programming to a 4-year-old?

Please find below top 50 common data structure problems

that can be solved using Dynamic programming -

1. Longest Common Subsequence | Introduction & LCS

Length

2. Longest Common Subsequence | Finding all LCS

3. Longest Common Substring problem

4. Longest Palindromic Subsequence using Dynamic
Programming

5. Longest Repeated Subsequence Problem

6. Implement Diff Utility

7. Shortest Common Supersequence | Introduction & SCS

Length

8. Shortest Common Supersequence | Finding all SCS

9. Longest Increasing Subsequence using Dynamic

Programming

10. Longest Bitonic Subsequence

11. Increasing Subsequence with Maximum Sum

12. The Levenshtein distance (Edit distance) problem

13. Find size of largest square sub-matrix of 1’s present in

given binary matrix

14. Matrix Chain Multiplication using Dynamic

Programming

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

16. Find longest sequence formed by adjacent numbers in

the matrix

17. Count number of paths in a matrix with given cost to

reach destination cell
18. 0–1 Knapsack problem

19. Maximize the Value of an Expression

20. Partition problem | Dynamic Programming Solution

21. Subset Sum Problem

22. Minimum Sum Partition Problem

23. Find all N-digit binary strings without any consecutive

1’s

24. Rod Cutting Problem

25. Maximum Product Rod Cutting

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

27. Coin Change Problem (Total number of ways to get the

denomination of coins)

28. Longest Alternating Subsequence Problem

29. Count number of times a pattern appears in given string

as a subsequence

30. Collect maximum points in a matrix by satisfying given

constraints

31. Count total possible combinations of N-digit numbers in

a mobile keypad

32. Find Optimal Cost to Construct Binary Search Tree

33. Word Break Problem | Dynamic Programming

34. Word Break Problem | Using Trie Data Structure

35. Total possible solutions to linear equation of k variables

36. Wildcard Pattern Matching

37. Find Probability that a Person is Alive after Taking N

steps on an Island

38. Calculate sum of all elements in a sub-matrix in constant

time

39. Find Maximum Sum Submatrix in a given matrix

40. Find Maximum Sum Submatrix present in a given matrix

41. Find maximum sum of subsequence with no adjacent

elements

42. Maximum Subarray Problem (Kadane’s algorithm)

43. Single-Source Shortest Paths — Bellman Ford Algorithm

44. All-Pairs Shortest Paths — Floyd Warshall Algorithm

45. Pots of Gold Game using Dynamic Programming

46. Find minimum cuts needed for palindromic partition of a

string

47. Maximum Length Snake Sequence

48. 3-Partition Problem

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

50. Check if given string is interleaving of two other given
strings