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

page1.House Robberpage2.Climbing Stairspage11.Longest Consecutive Sequencepage20. Uncrossed Linespage24. Decode Wayspage38. 2 Keys Keyboardpage44. 0-1 Knapsackpage48.Jump Gamepage55. Partition Array for Maximum Sum

Longest Increasing Subsequence variants:

page9.Longest Increasing Subsequencepage29. Longest String Chainpage30. Maximum Length of Pair Chainpage42. Number of Longest Increasing Subsequencepage43. Russian Doll Envelopespage50. Length of Longest Fibonacci Subsequencepage54. Best Team With No Conflicts

Partition Subset / Target Sum:

page15.Partition Equal Subset Sumpage16. Last Stone Weight IIpage14.Target Sumpage35. Partition to K Equal Sum Subsets

Palindrome:

page3.Longest Palindromic Substringpage4.Longest Palindromic Subsequencepage39. Palindrome Partitioning IIpage47. Minimum Insertion Steps to Make a String Palindromepage52. Palindromic Substrings

Matrix/2D Array:

page7.Unique Pathspage8.Minimum Path Sumpage22. Maximal Squarepage31. Minimum Falling Path Sumpage37. Count Square Submatrices with All Ones

Minimax DP:

page32. Predict the Winnerpage33. Delete and Earn

Longest Common Subsequence Variant:

page10.Longest Common Subsequencepage28. Maximum Length of Repeated Subarraypage49. Shortest Common Supersequencepage53. Distinct Subsequences

Coin Change variant:

page12.Coin Changepage13.Coin Change 2page23. Perfect Squarespage25. Minimum Cost For Ticketspage56. Ones and Zeroes

State machine:

page5.Best Time to Buy and Sell Stockpage6.Best Time to Buy and Sell Stock with Cooldownpage51. Maximum Alternating Subsequence Sum

Matrix multiplication variant:

page19.Burst Balloons

Dp on Strings

page17.Word Breakpage18. Word Break IIpage21. Wildcard Matchingpage27. Delete Operation for Two Stringspage36. Different Ways to Add Parenthesespage45. Interleaving Stringpage46. Edit Distance

Unbounded Knapsack:

page40. Integer Breakpage41.Cutting a Rod

Dp on Trees:

page34. House Robber III