Dynamic Programming 2D - Full Course - Python

Checkout my second Channel: @NeetCodeIO

0:00 - Intro
1:10 - Unique Paths
11:48 - Longest Common Subsequence
30:00 - Best Time to Buy/Sell Stock with Cooldown
45:01 - Coin Change II
1:08:12 - Target Sum
1:20:07 - Interleaving String
1:39:19 - Longest Increasing Path in a Matrix
1:55:53 - Distinct Subsequences
2:07:10 - Edit Distance
2:27:55- Burst Balloons
2:49:01 - Regular Expression Matching

#leetcode #neetcode #python

[learningalgos]

I’m convinced your stuff is better than Algoexpert

[sukanyasaha]

Woow this is gem. Can you please please do a comprehensive video on Graph?

[dorothychristina]

Hi Bro.Please do a full course on graph problems .It would be really helpful.This video is awesome 👌

[chukwunta]

This is such an amazing resource. Finally I now understand 2D DP better. Thanks so much. I truly appreciate all your effort, you have bee a great asset to my journey through this algo-verse.

[JJCUBER]

For the first problem, you can think of it as a scenario where you have letters that are r’s and d’s for the directions and the order of these matter. In the example, you would have 6 r’s and 2 d’s. You want to find all the possible orderings of these letters as a string/sequence. You do this by fixing the r’s then d’s (or the other way around). This means you would get (6+2) choose 2 * 6 choose 6. This is the same as 8 choose 2, which is 8*7/2=28. In general, it would be (n + m - 2) choose (n-1). You could also use (m-1) and can find the min of n and m to find out which calculation would be faster.

[uma_]

Hey, I received an offer from Amazon for SDE 2 role. I have been following you for long time now. You have a fair share in my success. Keep doing the great job.

[kashishsingh]

Ohh Man...you are great
Finally ....someone making so much comprehensive course on 2d mtrix

[mlguy]

First problem you can use combinatorics - because you know you know you have to go m moves across and n down. But if you want to have any blockers or if you allowed up and down this does not hold

[彭程-uk]

As a freshman in CS, dp is such a tall ask for me to overcome. And this series save me... respect for neetcode!

[yuemingpang]

Thank you very nice course on 2D dp! Just a reminder, there is a typo in the disctinct subsequences section:

dfs(i+i, j) should be dfs(i+1, j)



Thank you!

[pvhung]

I want to ask, what is your thought process when youre comming up with the solution?
I cant seem to figure out what to use when solving the problems.

[foxher]

A lot of these videos handwave things away, but these are really good solutions. Cheers

[nipunramani]

For Distinct Subsequences(2:06:10) use modulo on line 14 like this to get the correct answer when length of s is too long:
if(s[i] == t[j]):
cache[(i, j)] = dfs(i + 1, j + 1)%m + dfs(i + 1, j)%m


here m = int(1e9+7)

[hikmetdemir]

Could you please make an example training video for backtracking, graphs, tree and sliding window, starting from easy level to difficult level, just like you do for dynamic programming?

[raghuthetraveler]

Your explanation is better than anything i have see online

[satapa]

typo in the problem Distinct subsequences. It should be dfs(i+1, j) instead of dfs(i+i, j) in line 14 and 16

[animateforfun]

well, now I know a little bit more a bout caching in dp now, thanks

[madhumithakolkar_]

There's actually a mistake at 2:06:00 for the problem - Distinct Subsequences, great explanation by the way ! While you've mentioned it properly, there's a typo in the code >> cache[(i, j)] = dfs(i+1, j+1)+dfs(i+i, j) This should be dfs(i+1, j), you have mentioned it as i+i in all the places.

[brayn]

Explanations are good, but as someone who always wants to try and find out complete solution myself, it does take time for me and it does get a bit demotivating, so my question to you is that, did you figure out solutions to all problems by yourself or you took help or how did you approach these programming questions? Hope to get an answer.

[sophiophile]

For the first problem, I guess the only optimization (beyond knowing the math eq) would be selecting the smaller of m and n, so that your memory complexity is minimized.