Dynamic Programming

Majority of the Dynamic Programming problems can be categorized into two types:

1. Optimization problems. 2. Combinatorial problems.

• The optimization problems expect you to select a feasible solution, so that the value of the required function is minimized or maximized.

• Combinatorial problems expect you to figure out the number of ways to do something, or the probability of some event happening.

Linear and Misc Dp Questions

1.House Robber2.Climbing Stairs11.Longest Consecutive Sequence20. Uncrossed Lines24. Decode Ways38. 2 Keys Keyboard44. 0-1 Knapsack48.Jump Game55. Partition Array for Maximum Sum

Longest Increasing Subsequence variants:

9.Longest Increasing Subsequence29. Longest String Chain30. Maximum Length of Pair Chain42. Number of Longest Increasing Subsequence43. Russian Doll Envelopes50. Length of Longest Fibonacci Subsequence54. Best Team With No Conflicts

Partition Subset / Target Sum:

15.Partition Equal Subset Sum16. Last Stone Weight II14.Target Sum35. Partition to K Equal Sum Subsets

Palindrome:

3.Longest Palindromic Substring4.Longest Palindromic Subsequence39. Palindrome Partitioning II47. Minimum Insertion Steps to Make a String Palindrome52. Palindromic Substrings

Matrix/2D Array:

7.Unique Paths8.Minimum Path Sum22. Maximal Square31. Minimum Falling Path Sum37. Count Square Submatrices with All Ones

Minimax DP:

32. Predict the Winner33. Delete and Earn

Longest Common Subsequence Variant:

10.Longest Common Subsequence28. Maximum Length of Repeated Subarray49. Shortest Common Supersequence53. Distinct Subsequences

Coin Change variant:

12.Coin Change13.Coin Change 223. Perfect Squares25. Minimum Cost For Tickets56. Ones and Zeroes

State machine:

5.Best Time to Buy and Sell Stock6.Best Time to Buy and Sell Stock with Cooldown51. Maximum Alternating Subsequence Sum

Matrix multiplication variant:

19.Burst Balloons

Dp on Strings

17.Word Break18. Word Break II21. Wildcard Matching27. Delete Operation for Two Strings36. Different Ways to Add Parentheses45. Interleaving String46. Edit Distance

Unbounded Knapsack:

40. Integer Break41.Cutting a Rod

Dp on Trees:

34. House Robber III