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.
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 |