60 DYNAMIC PROGRAMMING INTERVIEW QUESTIONS

Certainly! Here are the most important 60 dynamic programming interview questions:

1. Coin Change Problem
2. Knapsack Problem
3. Binomial Coefficient Problem
4. Permutation Coefficient Problem
5. Program for nth Catalan Number
6. Matrix Chain Multiplication
7. Edit Distance
8. Subset Sum Problem
9. Friends Pairing Problem
10. Gold Mine Problem
11. Assembly Line Scheduling Problem
12. Painting the Fence problem
13. Maximize The Cut Segments
14. Longest Common Subsequence
15. Longest Repeated Subsequence
16. Longest Increasing Subsequence
17. Space Optimized Solution of LCS
18. LCS (Longest Common Subsequence) of three strings
19. Maximum Sum Increasing Subsequence
20. Count all subsequences having a product less than K
21. Longest subsequence such that the difference between adjacent is one
22. Maximum subsequence sum such that no three are consecutive
23. Egg Dropping Problem
24. Maximum Length Chain of Pairs
25. Maximum size square sub-matrix with all 1s
26. Maximum sum of pairs with specific difference
27. Min Cost Path Problem
28. Maximum difference of zeros and ones in a binary string
29. Minimum number of jumps to reach the end
30. Minimum cost to fill given weight in a bag
31. Minimum removals from an array to make max – min <= K
32. Longest Common Substring
33. Count the number of ways to reach a given score in a game
34. Count Balanced Binary Trees of Height h
35. Largest Sum Contiguous Subarray [V>V>V>V IMP]
36. Smallest sum contiguous subarray
37. Unbounded Knapsack (Repetition of items allowed)
38. Word Break Problem
39. Largest Independent Set Problem
40. Partition problem
41. Longest Palindromic Subsequence
42. Count All Palindromic Subsequence in a given String
43. Longest Palindromic Substring
44. Longest alternating subsequence
45. Weighted Job Scheduling
46. Coin game winner where every player has three choices
47. Count Derangements (Permutation such that no element appears in its original position) [IMPORTANT]
48. Maximum profit by buying and selling a share at most twice [IMP]
49. Optimal Strategy for a Game
50. Optimal Binary Search Tree
51. Palindrome Partitioning Problem
52. Word Wrap Problem
53. Mobile Numeric Keypad Problem [IMP]
54. Boolean Parenthesization Problem
55. Largest rectangular sub-matrix whose sum is 0
56. Largest area rectangular sub-matrix with an equal number of 1’s and 0’s [IMP]
57. Maximum sum rectangle in a 2D matrix
58. Maximum profit by buying and selling a share at most k times
59. Find if a string is interleaved of two other strings
60. Maximum Length of Pair Chain