Dynamic Programming Interview Questions and Practice Problems

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'”

In this post, we have list out commonly asked interview questions that can be solved using Dynamic programming –


  1. Introduction to Dynamic Programming
  2. Longest Common Subsequence | Introduction & LCS Length
  3. Longest Common Subsequence | Space optimized version
  4. Longest Common Subsequence of K-sequences
  5. Longest Common Subsequence | Finding all LCS
  6. Longest Common Substring problem
  7. Longest Palindromic Subsequence using Dynamic Programming
  8. Longest Repeated Subsequence problem
  9. Implement Diff Utility
  10. Shortest Common Supersequence | Introduction & SCS Length
  11. Shortest Common Supersequence | Finding all SCS
  12. Shortest Common Supersequence | Using LCS
  13. Longest Increasing Subsequence using Dynamic Programming
  14. Longest Bitonic Subsequence
  15. Increasing Subsequence with Maximum Sum
  16. The Levenshtein distance (Edit distance) problem
  17. Find size of largest square sub-matrix of 1’s present in given binary matrix
  18. Matrix Chain Multiplication
  19. Find the minimum cost to reach last cell of the matrix from its first cell
  20. Find longest sequence formed by adjacent numbers in the matrix
  21. Count number of paths in a matrix with given cost to reach destination cell
  22. 0-1 Knapsack problem
  23. Maximize value of the expression
  24. Partition problem
  25. Subset sum problem
  26. Minimum Sum Partition problem
  27. Find all N-digit binary strings without any consecutive 1’s
  28. Rod Cutting
  29. Maximum Product Rod Cutting
  30. Coin change-making problem (unlimited supply of coins)
  31. Coin Change Problem – Find total number of ways to get the denomination of coins
  32. Total possible solutions to linear equation of k variables
  33. Longest alternating subsequence
  34. Count number of times a pattern appears in given string as a subsequence
  35. Collect maximum points in a matrix by satisfying given constraints
  36. Count total possible combinations of N-digit numbers in a mobile keypad
  37. Find optimal cost to construct binary search tree
  38. Word Break Problem
  39. Word Break Problem | Using Trie Data Structure
  40. Determine Minimal Adjustment Cost of an Array
  41. Check if a string is K-Palindrome or not
  42. Find total ways to achieve given sum with n throws of dice having k faces
  43. Wildcard Pattern Matching
  44. Find probability that a person is alive after taking N steps on the island
  45. Calculate sum of all elements in a sub-matrix in constant time
  46. Find maximum sum K x K sub-matrix in a given M x N matrix
  47. Find maximum sum submatrix present in a given matrix
  48. Find maximum sum of subsequence with no adjacent elements
  49. Maximum subarray problem (Kadane’s algorithm)
  50. Single-Source Shortest Paths – Bellman Ford Algorithm
  51. All-Pairs Shortest Paths – Floyd Warshall Algorithm
  52. Longest Decreasing Subsequence Problem
  53. Pots of Gold Game using Dynamic Programming
  54. Find minimum cuts needed for palindromic partition of a string
  55. Maximum Length Snake Sequence
  56. 3 Partition Problem
  57. Calculate size of the largest plus of 1’s in binary matrix
  58. Check if given string is interleaving of two other given strings
  59. Longest Increasing Subsequence using LCS
  60. Determine negative-weight cycle in a graph


Thank you for being with us. 🙂


Leave a Reply

Notify of