Dynamic Programming can be described as storing answers to various sub-problems to be used later whenever required to solve the main problem.
The two common dynamic programming approaches are:
- Memoization: Known as the “top-down” dynamic programming, usually the problem is solved in the direction of the main problem to the base cases.
- Tabulation: Known as the “bottom-up ” dynamic programming, usually the problem is solved in the direction of solving the base cases to the main problem.
This post contains some hand-picked questions by Striver to learn or master Dynamic Programming. The post contains popular dynamic programming problems along with a detailed tutorials (both text and video). You can also practice the problem on the given link before jumping straight to the solution.
- Software Engineer at Google .
- Offers from Facebook London and other startups.
- Previously worked with Amazon, Media.net .
- Followed by 1M+ people across YT, Linkedin and other socials.
- Candidate Master at Codeforces.
- 6* at Codechef.
If you still have doubts or questions, we’ve got you covered! Check out our FAQs section at the bottom of the page, where we address some common queries that might help clarify any concerns you have.
Note: Only start solving the problems, if you have prior knowledge of DSA, in case you are a beginner please switch to Strivers A2Z DSA Sheet.
Part 1: Introduction to DP
Find both C++/Java codes of all problem in the articles in the first column.
| Topic | Video Solution | Practice Link 1 | Practice Link 2 | |
|---|---|---|---|---|
| Dynamic Programming Introduction | Link | Link | Link |
Part 2: 1D DP
Find both C++/Java codes of all problem in the articles in the first column.
| Topic | Video Solution | Practice Link 1 | Practice Link 2 | |
|---|---|---|---|---|
| Climbing Stars | Link | Link | Link | |
| Frog Jump(DP-3) | Link | Link | Link | |
| Frog Jump with k distances(DP-4) | Link | Link | Link | |
| Maximum sum of non-adjacent elements (DP 5) | Link | Link | Link | |
| House Robber (DP 6) | Link | Link | Link |
Part 3: 2D/3D DP and DP on Grids
Find both C++/Java codes of all problem in the articles in the first column.
Part 4: DP on Subsequences
Find both C++/Java codes of all problem in the articles in the first column.
Part 5: DP on Strings
Find both C++/Java codes of all problem in the articles in the first column.
Part 6: DP on Stocks
Find both C++/Java codes of all problem in the articles in the first column.
| Topic | Video Solution | Practice Link 1 | Practice Link 2 | |
|---|---|---|---|---|
| Best Time to Buy and Sell Stock |(DP-35) | Link | Link | Link | |
| Buy and Sell Stock – II|(DP-36) | Link | Link | Link | |
| Buy and Sell Stocks III|(DP-37) | Link | Link | Link | |
| Buy and Stock Sell IV |(DP-38) | Link | Link | Link | |
| Buy and Sell Stocks With Cooldown|(DP-39) | Link | Link | Link | |
| Buy and Sell Stocks With Transaction Fee|(DP-40) | Link | Link | Link |
Part 7: DP on LIS
Find both C++/Java codes of all problem in the articles in the first column.
| Topic | Video Solution | Practice Link 1 | Practice Link 2 | |
|---|---|---|---|---|
| Longest Increasing Subsequence |(DP-41) | Link | Link | Link | |
| Printing Longest Increasing Subsequence|(DP-42) | Link | Link | Link | |
| Longest Increasing Subsequence |(DP-43) | Link | Link | Link | |
| Largest Divisible Subset|(DP-44) | Link | Link | Link | |
| Longest String Chain|(DP-45) | Link | Link | Link | |
| Longest Bitonic Subsequence |(DP-46) | Link | Link | Link | |
| Number of Longest Increasing Subsequences|(DP-47) | Link | Link | Link |
Part 8: MCM DP | Partition DP
Find both C++/Java codes of all problem in the articles in the first column.
Part 9: DP on Squares
Find both C++/Java codes of all problem in the articles in the first column.
| Topic | Video Solution | Practice Link 1 | Practice Link 2 | |
|---|---|---|---|---|
| Maximum Rectangle Area with all 1’s|(DP-55) | Link | Link | Link | |
| Count Square Submatrices with All Ones|(DP-56) | Link | Link | Link |