The Last Dynamic Programming Video You'll Need to Watch

This 1.5 hour long video is all you need to know to get started to master dynamic programming. Kevin and Sheldon go to great detail to explain the top patterns from intuition to problem solving. Follow along and you will develop a strong intuition by going through this tutorial.

Intro and Overview: (0:00)
Pattern 1, Warm up problem : (1:13)
Pattern 2, Constant transition(7:03)
Pattern 3, Grid: (14:21)
Pattern 4, Two Sequences: (22:21)
Pattern 5, Interval: (34:51)
Pattern 6, Longest Increasing Subsequence, N^2 transition: (52:21)
Pattern 7, Knapsack-like: (1:08:23)

The playlist includes the following problems:
LeetCode 70. Climbing Stairs
LeetCode 746. Min Cost Climbing Stairs
LeetCode 62. Unique Paths
LeetCode 1143. Longest Common Subsequence
LeetCode 516. Longest Palindromic Subsequence
LeetCode 1395. Count Number of Teams
LeetCode 416. Partition Equal Subset Sum (Knapsack and Coin Change Problem)

[davidespinosa]

DP = recursion + memoization. So you're showing recursion (divide-and-conquer) for various data structures. Memoization avoids duplicate work on shared subproblems. Good job.

[phoneix]

The mandatory things to be good at before you start dp are recursion, trees, and backtracking. Its not that you cannot understand dp without these but these will make your dp journey easier.

How I started with DP and tried to remember/solve.

1. A function will do a computation. Consider it as a machine that takes input and gives an output. The machine can summon itself by changing its inputs, and passing over those.
2. This function might need to make some changes to the input it received and pass on further for processing (using itslef). Like a backpropagation.
3. Whatever you intend to return from the function, gets stored in the dp table cell.
4. Whatever input is changing (generally 2 for a 2d dp), is you dp rows and columns.
5. Rows are generally your given input. Generally the input is an array or a list (or a string which is a char array).
6. Remember, the rows in a dp table are number of elements (not index of the input array/list). So a 0 index in dp table means, what if the input was an empty array/list.

You could solve basic dp problems like subset sum and LCS with this. Once you builda base, the next problems will be relatable.
Dp problems are mostly optimization problems. And almost all optimization problems have one thing in common: do i use this particular value or I dont.

[valner]

The best video on the whole channel. Great intro to the DP problems

[theblacktechexperience]

This is by far the best (and most painful😂) video on dp. I need to lie down

[kevinbarnett]

I don't understand why the didn't just use the same algorithm for finding the longest common sub-sequence for the longest palindrome sub-sequence. Should just be able to take the input string as string 1, reverse it and then run the same code for the two strings.

[mcbotface]

You don't have to figure out the second dimension for the last problem because, we can solve it with a 1D array.
Here's the code.

class Solution:
def canPartition(self, nums: List[int]) -> bool:
ts = sum(nums)
n = len(nums)
if ts%2:
return False
ss = ts//2
dp = [0]*(ss+1)
for j in nums:
for i in range(ss, -1, -1):
if dp[i]==1 and i+j<=ss:
dp[i+j]=1
if j==i:
dp[i]=1
return True if dp[ss] else False

[rajrsa]

Thanks for this!

I am trying to understand this by converting the code to python and kinda stuck...
At 13:37, you used vector<int>dp(n+1). What does that mean for the initial values of dp?
I can't create a blank array of size n using python afaik. So, what should be the initial values of the dp array?

Also, imho, people who are using C++ for programming interviews will not be watching these types of videos lol

[ShahriyarRzayev]

Longest Palindromic Subsequence motivates us to drink and forget xd

[shubhanshumishra]

The code you wrote for the problem "1043. Partition Array for Maximum Sum" isn't giving the right output.

[VarunRao-kc]

int prev1=1, prev2=1, cur=0;
for(int i=2; i<=n; i++){
cur = (prev1+prev2) %
prev2=prev1;
prev1=cur;
}
return cur;

[abilashabi]

Tiny Code:


class Solution {
public int climbStairs(int n) {
int one = 1, two = 1;
for (int i = 2; i <= n; i++, two += one, one = two - one) {
}
return two;
}
}