Dynamic Programming – Interview Questions and Practice Problems

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.

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

1. Introduction to Dynamic ProgrammingBeginner
2. Longest Common Subsequence ProblemMedium
3. Longest Common Subsequence (LCS) | Space optimized versionMedium
4. Longest Common Subsequence of k–sequencesMedium
5. Longest Common Subsequence | Finding all LCSHard
6. Longest Common Substring ProblemMedium
7. Longest Palindromic Subsequence using Dynamic ProgrammingMedium
8. Longest Repeated Subsequence ProblemMedium
9. Implement Diff UtilityMedium
10. Shortest Common Supersequence ProblemMedium
11. Shortest Common Supersequence | Finding all SCSHard
12. Shortest Common Supersequence Problem using LCSHard
13. Longest Increasing Subsequence using Dynamic ProgrammingHard
14. Longest Decreasing Subsequence ProblemHard
15. Longest Bitonic SubsequenceMedium
16. Maximum Sum Increasing Subsequence ProblemMedium
17. The Levenshtein distance (Edit distance) ProblemMedium
18. Find the size of the largest square submatrix of 1’s present in a binary matrixMedium
19. Matrix Chain Multiplication using Dynamic ProgrammingHard
20. Find minimum cost to reach the last cell of a matrix from its first cellMedium
21. Find the longest sequence formed by adjacent numbers in the matrixMedium
22. Count the number of paths in a matrix with a given cost to reach the destination cellMedium
23. 0–1 Knapsack ProblemMedium
24. Maximize the value of an expressionHard
25. Partition Problem using Dynamic ProgrammingMedium
26. Subset Sum Problem – Dynamic Programming SolutionMedium
27. 3–Partition ProblemMedium
28. Minimum Sum Partition ProblemHard
29. Rod Cutting ProblemMedium
30. Maximum Product Rod CuttingMedium
31. Coin change-making problemMedium
32. Coin Change ProblemHard
33. Total possible solutions to a linear equation of k variablesHard
34. Longest Alternating Subsequence ProblemMedium
35. Count the number of times a pattern appears in a given string as a subsequenceHard
36. Collect maximum points in a matrix by satisfying given constraintsHard
37. Find all N-digit binary strings without any consecutive 1’sEasy
38. Count total possible combinations of n-digit numbers in a mobile keypadMedium
39. Word Break Problem – Dynamic ProgrammingHard
40. Determine the minimal adjustment cost of an arrayHard
41. Check if a string is k–palindrome or notHard
42. Find total ways to achieve a given sum with n throws of dice having k facesMedium
43. Wildcard Pattern MatchingHard
44. Find the number of ways to fill an N × 4 matrix with 1 × 4 tilesMedium
45. Ways to reach the bottom-right corner of a matrix with exactly k turns allowedHard
46. Weighted Interval Scheduling ProblemMedium
47. Box Stacking ProblemHard
48. Find total ways to reach n’th stair with at-most m stepsMedium
49. Find total ways to reach the n’th stair from the bottomMedium
50. Activity Selection Problem using Dynamic ProgrammingMedium
51. Find the minimum number of deletions required to convert a string into a palindromeMedium
52. Calculate the minimum cost to reach the destination city from the source cityMedium
53. Pots of Gold Game Problem using Dynamic ProgrammingHard
54. Find minimum cuts needed for the palindromic partition of a stringHard
55. Weighted Interval Scheduling – Dynamic Programming SolutionMedium
56. Find minimum jumps required to reach the destinationMedium
57. Find the probability that a person is alive after taking n steps on an islandMedium
58. Maximum Length Snake SequenceMedium
59. Calculate the size of the largest plus of 1’s in a binary matrixHard
60. Longest Increasing Subsequence using LCSMedium
61. Find maximum profit earned from at most k stock transactionsHard
62. Count all paths in a matrix from the first cell to the last cellEasy
63. Check if a string matches with the given wildcard patternHard
64. Check if a string is interleaving of two other given stringsMedium
65. Find all employees who directly or indirectly reports to a managerHard
66. Find optimal cost to construct a binary search treeHard
67. Find the maximum sum of a subsequence with no adjacent elementsMedium
68. Minimum-weight triangulation of a convex polygonHard
69. Find maximum profit that can be earned by conditionally selling stocksEasy
70. Program to find n’th Fibonacci numberEasy
71. Count decodings of a given sequence of digitsMedium
72. Hat Check Problem – Counting DerangementsMedium
73. Maximum Independent Set ProblemMedium
74. Find the minimum number of squares that sum to a given numberMedium
75. Truncate an integer array such that 2×min becomes more than maxHard
76. Maximum Sum Subarray Problem (Kadane’s Algorithm)Easy
77. Longest Alternating Subarray ProblemEasy
78. Find maximum profit earned from at most two stock transactionsHard
79. Find ways to calculate a target from elements of the specified arrayMedium
80. Calculate the sum of all elements in a submatrix in constant timeMedium
81. Find maximum sum K × K submatrix in a given M × N matrixHard
82. Find maximum sum submatrix present in a matrixMedium
83. Find the length of the longest path in a matrix with consecutive charactersMedium
84. Collect maximum value of coins in a matrixHard
85. Single-Source Shortest Paths – Bellman–Ford AlgorithmMedium
86. All-Pairs Shortest Paths – Floyd Warshall AlgorithmEasy
87. Determine a negative-weight cycle in a graphMedium
88. Word Break Problem – Using Trie Data StructureMedium