Top 50 Dynamic Programming Practice Problems

Vivek Srivastava
Techie Delight
3 min readAug 3, 2018

--

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

--

--