Dynamic Programming

Knapsack, paths, sequences, partitions and counting.

56 problems

Title	Tags	Acceptance	Difficulty
1. Best Subarray with Bounds	Kadane	—	Medium
2. Count Palindromic Substrings	Expand Around Centre	—	Medium
3. Decode Ways	Dynamic Programming	—	Medium
4. Valid Interleaving	Dynamic Programming	—	Hard
5. N-th Fibonacci Modulo	Fast Doubling · Matrix Power	—	Medium
6. Catalan Number	Combinatorics	—	Medium
7. N-th Ugly Number	Dynamic Programming	—	Medium
8. Sum of All Digits 1..N	Digit DP	—	Hard
9. Longest Valid Parentheses	Stack	—	Hard
10. Subset Sum	Dynamic Programming	—	Medium
11. Grid Paths	Combinatorics · Recursion	—	Easy
12. House Robber	Dynamic Programming	—	Medium
13. House Robber (Circle)	Dynamic Programming	—	Medium
14. Min Cost Climbing Stairs	Dynamic Programming	—	Easy
15. Grid Paths with Obstacles	Dynamic Programming · Grid	—	Medium
16. Minimum Path Sum	Dynamic Programming · Grid	—	Medium
17. Triangle Minimum Path	Dynamic Programming	—	Medium
18. 0/1 Knapsack	Knapsack	—	Medium
19. Unbounded Knapsack	Knapsack	—	Medium
20. Coin Change — Number of Ways	Dynamic Programming · Counting	—	Medium
21. Longest Common Substring	Dynamic Programming	—	Medium
22. Longest Palindromic Subsequence	Dynamic Programming	—	Medium
23. Minimum Insertions for Palindrome	Dynamic Programming	—	Medium
24. Word Break	Dynamic Programming	—	Medium
25. Partition Equal Subset Sum	Knapsack	—	Medium
26. Target Sum with Signs	Dynamic Programming · Counting	—	Medium
27. Number of Longest Increasing Subsequences	Dynamic Programming	—	Hard
28. Maximum Product Subarray	Dynamic Programming	—	Medium
29. Jump Game	Greedy	—	Medium
30. Minimum Jumps	Greedy · BFS	—	Medium
31. Rod Cutting	Dynamic Programming	—	Medium
32. Egg Dropping	Dynamic Programming	—	Hard
33. Matrix Chain Multiplication	Interval DP	—	Hard
34. Ways to Make an Expression	Interval DP	—	Hard
35. Paint the Fence	Dynamic Programming · Counting	—	Medium
36. Count Binary Search Trees	Catalan	—	Medium
37. Dice Sum Ways	Dynamic Programming · Counting	—	Medium
38. Longest Bitonic Subsequence	Dynamic Programming	—	Medium
39. Largest Square of Ones	Dynamic Programming · Grid	—	Medium
40. Distinct Subsequence Count	Dynamic Programming · Counting	—	Hard
41. Wildcard Matching	Dynamic Programming	—	Hard
42. Regular Expression Matching	Dynamic Programming	—	Hard
43. Stock Trading with Cooldown	State Machine DP	—	Medium
44. Stock Trading with K Transactions	Dynamic Programming	—	Hard
45. Minimum Subset Difference	Knapsack	—	Medium
46. Count Subsets with Sum	Knapsack · Counting	—	Medium
47. Longest Arithmetic Subsequence	Dynamic Programming · Hash Map	—	Medium
48. Frog Jump with K	Dynamic Programming	—	Easy
49. Vacation Plan	Dynamic Programming	—	Medium
50. Perfect Squares	Dynamic Programming	—	Medium
51. Binary Strings Without Consecutive Ones	Dynamic Programming · Fibonacci	—	Easy
52. Domino Tiling 2×N	Dynamic Programming	—	Easy
53. Max Sum without Three Consecutive	Dynamic Programming	—	Medium
54. Paths in a DAG	Topological Sort · DP	—	Medium
55. Set Bits for 0..N	Bits · DP	—	Easy
56. N-th Tribonacci Number	DP	—	Easy

56 of 56 problems