Everyone hates Dynamic Programming (DP). Yes, it's tough, but after practice, you realize that many DP problems follow a similar template.
It boils down to optimized recursion - we solve problems by breaking them down into smaller overlapping subproblems.
The optimization DP makes is after solving each subproblem, we store (or cache) the results in a table to avoid redundant computations.
Here are 4 common DP patterns:
1) 0/1 Knapsack - We must select items with maximum profit while respecting a weight constraint, with each item only available once to put into the knapsack.
3) Longest Common Subsequence - The problem of finding the longest sequence of characters that appears in the same order (not necessarily consecutively) within two or more given strings.
4) Number Of Unique Paths - Count the number of unique paths from the top left to the bottom right in a 2D grid, where we are only allowed to move down or to the right.
NeetCodeIO
Everyone hates Dynamic Programming (DP). Yes, it's tough, but after practice, you realize that many DP problems follow a similar template.
It boils down to optimized recursion - we solve problems by breaking them down into smaller overlapping subproblems.
The optimization DP makes is after solving each subproblem, we store (or cache) the results in a table to avoid redundant computations.
Here are 4 common DP patterns:
1) 0/1 Knapsack - We must select items with maximum profit while respecting a weight constraint, with each item only available once to put into the knapsack.
🟡 Target Sum - neetcode.io/problems/target-sum
2) Unbounded Knapsack - Similar to 0/1 knapsack, but each item can be selected multiple times to maximize profit without exceeding the weight limit.
🟡 Coin Change - neetcode.io/problems/coin-change
3) Longest Common Subsequence - The problem of finding the longest sequence of characters that appears in the same order (not necessarily consecutively) within two or more given strings.
🟡 LCS - neetcode.io/problems/longest-common-subsequence
🔴 Edit Distance - neetcode.io/problems/edit-distance
4) Number Of Unique Paths - Count the number of unique paths from the top left to the bottom right in a 2D grid, where we are only allowed to move down or to the right.
🟡 Unique Paths - neetcode.io/problems/count-paths
---
If you wanna learn these patterns more in-depth, I cover them in the Advanced Algorithms course on neetcode.io/ 🚀
5 months ago | [YT] | 1,120