Striver DP Series : Dynamic Programming Problems

Dynamic Programming Problems
Striver DP Series : Dynamic Programming Problems

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.

Topic Video Solution Practice Link 1 Practice Link 2
Ninja’s Training (DP 7) Link Link Link
Grid Unique Paths : DP on Grids (DP8) Link Link Link
Grid Unique Paths 2 (DP 9) Link Link Link
Minimum path sum in Grid (DP 10) Link Link Link
Minimum path sum in Triangular Grid (DP 11) Link Link Link
Minimum/Maximum Falling Path Sum (DP-12) Link Link Link
3-d DP : Ninja and his friends (DP-13) Link Link Link
Part 4: DP on Subsequences

Find both C++/Java codes of all problem in the articles in the first column.

Topic Video Solution Practice Link 1 Practice Link 2
Subset sum equal to target (DP- 14) Link Link Link
Partition Equal Subset Sum (DP- 15) Link Link Link
Partition Set Into 2 Subsets With Min Absolute Sum Diff (DP- 16) Link Link Link
Count Subsets with Sum K (DP – 17) Link Link Link
Count Partitions with Given Difference (DP – 18) Link Link Link
0/1 Knapsack (DP – 19) Link Link Link
Minimum Coins (DP – 20) Link Link Link
Target Sum (DP – 21) Link Link Link
Coin Change 2 (DP – 22) Link Link Link
Unbounded Knapsack (DP – 23) Link Link Link
Rod Cutting Problem | (DP – 24) Link Link Link
Part 5: DP on Strings

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 Common Subsequence | (DP – 25) Link Link Link
Print Longest Common Subsequence | (DP – 26) Link Link Link
Longest Common Substring | (DP – 27) Link Link Link
Longest Palindromic Subsequence | (DP-28) Link Link Link
Minimum insertions to make string palindrome | DP-29 Link Link Link
Minimum Insertions/Deletions to Convert String | (DP- 30) Link Link Link
Shortest Common Supersequence | (DP – 31) Link Link Link
Distinct Subsequences| (DP-32) Link Link Link
Edit Distance | (DP-33) Link Link Link
Wildcard Matching | (DP-34) Link Link Link
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.

Topic Video Solution Practice Link 1 Practice Link 2
Matrix Chain Multiplication|(DP-48) Link Link Link
Matrix Chain Multiplication | Bottom-Up|(DP-49) Link Link Link
Minimum Cost to Cut the Stick|(DP-50) Link Link Link
Burst Balloons|(DP-51) Link Link Link
Evaluate Boolean Expression to True|(DP-52) Link Link Link
Palindrome Partitioning – II|(DP-53) Link Link Link
Partition Array for Maximum Sum|(DP-54) Link Link Link
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