Dynamic Programming 1D - Full Course - Python

Checkout my second Channel: @NeetCodeIO

0:00 - Intro
1:05 - Climbing Stairs
19:03 - Min Cost Climbing Stairs
38:16 - House Robber
48:45 - House Robber II
58:58 - Longest Palindromic Substring
1:07:00 - Palindromic Substrings
1:21:51 - Decode Ways
1:37:08 - Coin Change
1:56:23 - Maximum Product Subarray
2:11:46 - Word Break
2:27:06 - Longest Increasing Subsequence
2:45:20 - Partition Equal Subset Sum

#neetcode #leetcode #python

[sherazdotnet]

I'd like to share a few points. With DP, one of the main challenge is how do you recognize a problem is indeed a DP problem. It can be misleading at times that a given problem is indeed a DP problem.
Therefore, I'd say that this course and more upcoming DP parts that you might be posting, would be great if you start each question with pure analysis of why this problem is a DP problem to begin with. Taking a view on the question as if it has never been seen and then you apply contain ideas to identify if its a DP problem or not.
The reason I'm bringing this point is because it just so happened that one of my friend shared his experience with me that he had a few years ago where during interview, he thought the problem is a DP and after 25 mins in the interview, he realized that's its not but he had waisted essentially all the critical time.

Long story short, would be great that for every question, would be great to talk about what attributes of such problem made it obvious that its a DP problem.

[temik]

You're doing amazing work for all who wants to be good at algorithms and pass interviews. Mad respect!

[mohammedumarfarhan]

Thanks a lot brother. May God bless you abundantly

[rohithboppey]

I'm not sure who needs this, but I guess we can use the similar format for all 1D problems-


class Solution {
public:
int solve(vector<int>& ways, int n, int start){
if(start >= n){
// no way to reach the end
return 0;
}

if(ways[start] != -1){
// already calculated
return ways[start];
}

// not cal
// need to cal

// it always depends on the next problem
return ways[start] = solve(ways, n, start + 1) + solve(ways, n, start + 2);
}

int climbStairs(int n) {
// using the concept of DP
vector<int> ways(n + 1, -1);

if(n < 2){
return 1;
}

ways[n] = 0;
ways[n-1] = 1;
ways[n-2] = 2;

// ways means number of ways we can reach the end
// if the start position is i

solve(ways, n, 0);
return ways[0];

}
};

[peekaboo]

Ohhh neetcode only if I could express how much I owe you for improving my problem solving skills

[xzex]

Climbing Stairs can be written in just three lines(instead of five), in python for swapping two variables you don't need a Temp variable, you can use
a, b = b, a or ( one, two = one + two, one )
class Solution:
def climbStairs(self, n: int) -> int:
one, two = 1, 1
for i in range(n-1):
one, two = one + two, one
return one

[reebaqureshi]

I've been watching your videos so much through my interview preparations that your voice sounds like a mother's lullaby to me at this point.

[zizzlindawg]

This is amazing, thanks for all the work you do.

[undergrad]

Dear Neetcode, thank you for uploading this. I have been following your content for quite some time and I really appreciate the effort you have put into creating content for DSA. However, I would really appreciate it if you could highlight the core in-depth reason for why such DP patterns exist, and how to identify them. So a template, instead of solutions.

[aniquatabassum]

In the climbing stairs problem, why is the value for the base case 1? If we are at the base case, then there are 0 ways to reach the base case right….? I realise if we initialise the base case to zero then the code won’t work. I just want to understand what other reason there is for the base case to be one.

[b]

I paid for the lifetime membership yesterday, but this super long and helpful video is just for free.
So, goodbye my money, I have to support this cool guy indeed.

[alexgabriel]

great stuff! hope for other topics covered the same way!

[sherazdotnet]

Here is my solution using Recursion + Memoization. Code is written in c#

public int CountSteps(int totalSteps, Dictionary<int, int> memo) {
if(totalSteps ==0) {
return 1;
}

if(totalSteps < 0) {
return 0;
}

{
return memo[totalSteps];
}

var usingOneStep = CountSteps(totalSteps-1, memo);
var usingTwoSteps = CountSteps(totalSteps-2, memo);

memo[totalSteps] = usingOneStep + usingTwoSteps;
return memo[totalSteps];
}

[house]

I agree, climbing stairs was indeed explained top notch.

[ErenTal]

Hello everyone!
I have a question regarding the problem 300 "Longest increasing subsequence". Why didn't we write:

LIS = [1] * (len(nums)+1) instead of LIS = [1] * len(nums)

For example, in the previous problem "Word Break" we've used the +1. In which cases do we use the +1 when we define dp and in which cases we do not?
Thank you

[jonathanpangilinanjr.]

Thank you very much for this video. I finally solved my very own medium dp lc after watching a quarter of your video. I'm gonna finish this and hopefully, I can stand on my own feet after.

[vikasjha]

Best playlist to learn DP. Thanks mate

[ujjawalpanchal]

@neetcode Props on the great video! Are palindromic substrings and longest palindromic substrings relevant to DP? If not, why are they in this compilation?

[bubblesort]

The best timing. İ was in need of this. Thank you so much Sir.

[Hossein]

Absolutely love your content. It’s so neet and easy to follow for the layman. Do you have a Rumble channel as well?