Study Plan: Dynamic Programming
Published:
This page is continually updated with new and improved content to ensure the best curation for Dynamic Programming problems.
Important Links:
- Source : Striver SDE Sheet,
- Ultimate Dynamic Programming Roadmap
- Youtube Link - DP Patterns (Coded)
- All DP Problems sorted patterwise
Pattern 1: 0/1 Knapsack (Bounded)
Solution is built upon subset, but with few more restrictions. For example you want to complete some courses, they have some reward points associated. But you can attend only k number of courses. Now try to maximize your points. This type of problems are just an extension to simple DP, where you add one more dimension to consider provided restriction.
Problems:
Pattern 2: 0/1 Knapsack (Unbounded)
Dp state is similar to the classical knapsack problem.
Problems:
Pattern 3: Fibonacci (or Linear DP)
You just need to find the repetitive part of the solution and improve it by saving its result.
Dp solution requires us to solve the sub problem on every prefix of the array. A prefix of the array is a subarray from 0 to i for some i.
Problems:
Pattern 4: String DP
Problems:
- Is Subsequence
- Palindromic Partitioning I
- Palindromic Partitioning II
- Word Break
- Longest Valid Parentheses
- Word Break II
- Concatenated Words
- Distinct Subsequences
Pattern 5: Longest Common Subsequence (LCS) [String DP]
Problems:
- Longest Common Subsequence
- Maximum length of repeated Subarray
- Edit Distance
- Interleaving String
- Longest Happy String
- Longest String Chain
- Shortest Common Supersequence
- Minimum Insertion Steps to Make a String Palindrome
Pattern 6: Palindromes (LCS)
Problems:
- Longest Palindromic Substring
- Longest Palindromic Subsequence
- Minimum Insertion Steps to make a string Palindrome
- Valid Palindrome III
- Palindromic Substrings
Pattern 7: Longest Increasing Subsequence (LIS)
Dp problem is solved on every prefix of the array. Transition is from every index j < i.
Problems:
- Longest Increasing Subsequence
- Russian Doll Envelops
- Number of Longest Increasing Subsequence
- Make Array Strictly Increasing
Pattern 8: Matrix Chain Multiplication
Dp problem is solved on every single interval (subarray) of the array.
Problems:
Pattern 9: Kadane’s Algorithm
Problems:
- Best Time to Buy and Sell Stock
- Maximum Subarray
- Maximum Product Subarray
- Longest Turbulent Subarray
- Largest Divisible Subset
Pattern 10: DP on Trees
Problems:
- Binary Tree Cameras
- Maximum Sum BST in Binary Tree
- Longest ZigZag Path in a Binary Tree
- House Robber III
- Unique Binary Search Trees II
Pattern 11: Grid DP
Dp table will have the same dimensions as grid, the state at cell i,j will be related to the grid at cell i,j.
Problems:
- Matrix Block Sum
- Dungeon Game
- Maximal Square
- Minimum Falling Path Sum
- Unique Paths
- Unique Paths II
- Minimum Path Sum