You are the best among leetcode solving youtube channels, others are not even close in quality of explanation... It would be nice if leetcode hire you to write content for "solution" tabs...
this is exactly how we should approach a problem - from the first principles. lots of other youtubers just copy paste a discussion solution without understanding what's happening. great stuff!
I think this is a better solution and more closely follows the first climbing stairs question, heres your solution if you cannot change the original array class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: a = cost[0] b = cost[1] for i in range(2, len(cost)): temp = b b = cost[i] + min(a,b) a = temp return min(a ,b)
Such a cool problem to learn about dynamic programming right after "Climbing Stairs". Your roadmap is GOATED! I've been grinding the "Neetcode All" and I've been having the time of my life.
it would be better for the brute force to start at an imaginary -1 index, so that you don't need to go through the decision tree again to get the following index's decision tree.
Nice video, but similar to the "Climbing Stairs" problem, I don't see a benefit from starting at the end of the array, and it makes it more confusing (even more so for this one than climbing stairs). Since you can start at 0 or 1 index, it is easy to simply say the answer to the next index is min(cost[i -1], cost[i - 2]) + cost[i] starting from i = 2. Since when we are at i, we always have to pay the cost of landing at i, whether we take 1 step or 2.
FYI, it isn't necessary to start by appending 0 to the list. But you can keep everything else the same and still start with length(list)-3, because the cost of the last 2 items will always be its own value
Great explanation! However, modifying the original input can be considered bad practice - what if the interviewer doesn't want that? Alternative answer, passes all test cases: def minCostClimbingStairs(self, cost: List[int]) -> int: one = two = 0 for i in range(2, len(cost) + 1): temp = one one = min(one + cost[i - 1], two + cost[i - 2]) two = temp return one
This is a better incremental understanding if you have learnt in sequence of Bottom Up for => fibonacci -> Climbing Stairs -> Now def stairsbu(): c = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] n = 10 i = 2 cache = [0, 0] while(i
Hey, you probably realize this by now. But you don't really need to append a 0 or start at 15 in the example you showed. You can just start at 10 in that example since the last 2 spots will never change since the end can be reached by either of those spots.
Climbing stairs is a symmetric problem so you can actually reverse the tree, which makes the code solution easier one, two = 0, 0 for i in range(2, len(cost) + 1): one, two = two, min(one + cost[i-2], two + cost[i-1]) return two
correct me if I'm wrong but we don't necessarily need to add the 0 because whenever we get to the n-2 index it is always better to make a doble jump rather than one jump. so cost of that index is its own value. so we start from n-3 and go toward the stat and don't need to update the n-2 value.
Tiny optimization but you don't have to start at len(arr)-3 you can start at len(arr)-4 bc the second to last element will never be smaller if it jumps to the last element first before the end of the staircase. It will always stay the same.
Instead of going from the end to the start we can go from the start to the end (without -1 in range) Code: class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: for x in range(2, len(cost)): cost[x] += min(cost[x-1], cost[x-2])
We can do it similar to the climbing stairs problem as follows class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: one, two = 0, 0 for i in range(len(cost)-1, -1, -1): cost[i] += min(one, two) two = one one = cost[i] return min(one, two)
We can make sure the last two min values should be themselves. So there is no need to append another 0 class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: #cost.append(0) for i in range(len(cost) - 3, -1, -1): cost[i] = min(cost[i] + cost[i + 1], cost[i] + cost[i + 2]) return min(cost[0], cost[1])
Slightly different approach that I came to on my end :P class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: for i in range(2, len(cost)): cost[i] = min(cost[i] + cost[i - 1], cost[i] + cost[i - 2]) return min(cost[-1], cost[len(cost) - 2])
I don't like that this solution mutates the original dataset. Also, I felt unsatisfied when you explained a DFS + memoization algorithm, but then coded an iterative solution instead. However, I was able to code my own solution using recursion + cache with your clear explanation, which personally I find more intuitive than iterating in reverse!
C++ code: int n=cost.size(); int dp[n+2]; dp[n+1]=0;dp[n]=0; int jumpCost1,jumpCost2; for(int i=n-1;i>=0;i--){ jumpCost1=cost[i]+dp[i+1]; jumpCost2=cost[i]+dp[i+2]; dp[i]=min(jumpCost1,jumpCost2); }
It's weird that the problem is called "climbing stairs". I mean, what stairs have one step being 100 times more expensive to climb that the previous one? Why didn't they call the problem "saving fuel on an airplane" or something.
your brute force solution misses the fact that we can start at either position 0 or position 1, we can run two seperate stack traces from each poisiton and get the min, or we can start jumping from position -1. the cost there is 0, and it can either jump to position 0 or position 1. my bruteforce code: def minCostClimbingStairs(self, cost: List[int]) -> int: minC = 10000000000000 def jump(n, c, minC): if n >= len(cost): minC = min(minC, c) return minC if n > -1: c += cost[n] return min(jump(n + 1, c, minC), jump(n + 2, c, minC)) return jump(-1, 0, minC)
💡 DYNAMIC PROGRAMMING PLAYLIST: ruclips.net/video/73r3KWiEvyk/видео.html
did you got a job at google or faang
You are the best among leetcode solving youtube channels, others are not even close in quality of explanation... It would be nice if leetcode hire you to write content for "solution" tabs...
I appreciate the kind words :)
this is exactly how we should approach a problem - from the first principles. lots of other youtubers just copy paste a discussion solution without understanding what's happening. great stuff!
we can also use top down solution with 3 lines of codes:
for i in range(2, len(cost)):
cost[i] += min(cost[i - 1], cost[i - 2])
return min(cost[-2:])
This is what I did.
if you're adding a 0 at the end like he did, you can just return cost[-1]. seems more easy to understand this way atleast for me
I think this is a better solution and more closely follows the first climbing stairs question, heres your solution if you cannot change the original array
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
a = cost[0]
b = cost[1]
for i in range(2, len(cost)):
temp = b
b = cost[i] + min(a,b)
a = temp
return min(a ,b)
How's it Top down? It's still bottom up right? Just the direction of iteration has reversed. But answer still depends on subproblem of i -1 and i -2?
You are an asset to the programming world. Thank you.
Such a cool problem to learn about dynamic programming right after "Climbing Stairs". Your roadmap is GOATED! I've been grinding the "Neetcode All" and I've been having the time of my life.
your channel is like a gift from God ngl
After explanation without watching coding part I solved this. Nice explanation.
Are DP questions really common on interviews? I feel like only Google would ask them, I got asked House Robber on their phone screen.
Thanks!
it would be better for the brute force to start at an imaginary -1 index, so that you don't need to go through the decision tree again to get the following index's decision tree.
Dude just... thanks. You are Abdul Bari level
A more compact implementation of the same algorithm:
cur = nxt = 0
for c in cost[::-1]:
cur, nxt = c + min(cur, nxt), cur
return min(cur, nxt)
Nice video, but similar to the "Climbing Stairs" problem, I don't see a benefit from starting at the end of the array, and it makes it more confusing (even more so for this one than climbing stairs). Since you can start at 0 or 1 index, it is easy to simply say the answer to the next index is min(cost[i -1], cost[i - 2]) + cost[i] starting from i = 2. Since when we are at i, we always have to pay the cost of landing at i, whether we take 1 step or 2.
FYI, it isn't necessary to start by appending 0 to the list. But you can keep everything else the same and still start with length(list)-3, because the cost of the last 2 items will always be its own value
Great explanation! However, modifying the original input can be considered bad practice - what if the interviewer doesn't want that?
Alternative answer, passes all test cases:
def minCostClimbingStairs(self, cost: List[int]) -> int:
one = two = 0
for i in range(2, len(cost) + 1):
temp = one
one = min(one + cost[i - 1], two + cost[i - 2])
two = temp
return one
This is a better incremental understanding if you have learnt in sequence of Bottom Up for => fibonacci -> Climbing Stairs -> Now
def stairsbu():
c = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
n = 10
i = 2
cache = [0, 0]
while(i
Hey, you probably realize this by now. But you don't really need to append a 0 or start at 15 in the example you showed. You can just start at 10 in that example since the last 2 spots will never change since the end can be reached by either of those spots.
This is what I did
This IS NOT an EASY problem for everyone!! should be marked as MEDIUM
You are a gift from god. Regretting why didn't I find you before
no one literally takes me through the dp this level except you ,thank you 🤞🤞🤞🤞🤞🤞🤞🤞
Climbing stairs is a symmetric problem so you can actually reverse the tree, which makes the code solution easier
one, two = 0, 0
for i in range(2, len(cost) + 1):
one, two = two, min(one + cost[i-2], two + cost[i-1])
return two
Thanks.
I think we don't need to add 0 at the end since the cost can't be negative.
correct me if I'm wrong but we don't necessarily need to add the 0 because whenever we get to the n-2 index it is always better to make a doble jump rather than one jump. so cost of that index is its own value. so we start from n-3 and go toward the stat and don't need to update the n-2 value.
for i in range(2,len(cost)):
cost[i]+=min(cost[i-1],cost[i-2])
return min(cost[-1],cost[-2])
Tiny optimization but you don't have to start at len(arr)-3 you can start at len(arr)-4 bc the second to last element will never be smaller if it jumps to the last element first before the end of the staircase. It will always stay the same.
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
for i in range(2, len(cost)):
cost[i] += min(cost[i - 1], cost[i - 2])
return min(cost[-1], cost[-2])
Instead of going from the end to the start we can go from the start to the end (without -1 in range)
Code:
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
for x in range(2, len(cost)):
cost[x] += min(cost[x-1], cost[x-2])
return min(cost[-2], cost[-1])
It is more readable, understandable, thank you!
NeetCode: yeah, that's the entire code...
Me: magic!!!
Great Explanation Thanks!!!
We can do it similar to the climbing stairs problem as follows
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
one, two = 0, 0
for i in range(len(cost)-1, -1, -1):
cost[i] += min(one, two)
two = one
one = cost[i]
return min(one, two)
We can make sure the last two min values should be themselves. So there is no need to append another 0
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
#cost.append(0)
for i in range(len(cost) - 3, -1, -1):
cost[i] = min(cost[i] + cost[i + 1], cost[i] + cost[i + 2])
return min(cost[0], cost[1])
top down + memo
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
dp = {} #{step:min_cost}
def helper(n):
if n == 0:
return cost[0]
if n == 1:
return cost[1]
if n in dp:
return dp[n]
one_step_cost = helper(n-1)+cost[n]
two_step_cost = helper(n-2)+cost[n]
min_cost = min(one_step_cost,two_step_cost)
dp[n] = min_cost
return min_cost
return min(helper(len(cost)-1),helper(len(cost)-2))
Maza aa raha hai dil garden garden ho raha hai ek bar mein 3eno se solve Kar liya
Your videos are my best find on the way to my dream!
Recursive solution:
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
cache = {}
def dfs(i):
if i >= len(cost):
return 0
elif i in cache:
return cache[i]
cache[i] = min(cost[i] + dfs(i + 1), cost[i] + dfs(i + 2))
return cache[i]
dfs(0)
return min(cache[0], cache[1])
Slightly different approach that I came to on my end :P
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
for i in range(2, len(cost)):
cost[i] = min(cost[i] + cost[i - 1], cost[i] + cost[i - 2])
return min(cost[-1], cost[len(cost) - 2])
3:00 was my first exact thought lol
thank you so much for providing such beautiful solutions!
Simply the Best!
I don't like that this solution mutates the original dataset. Also, I felt unsatisfied when you explained a DFS + memoization algorithm, but then coded an iterative solution instead. However, I was able to code my own solution using recursion + cache with your clear explanation, which personally I find more intuitive than iterating in reverse!
+1 I prefer the recursion + memoization version. The Tabulation version here seems a bit complex.
hey! I implemented the recursion + memoization version and it fails time limits on high load test cases. Can you show your version please?
thank you for walking through your thought process! only wish you were a java programmer... : )
craziest part, you dont even need to go reverse order
I liked the explanation
Great video
super intuition
Hi, I was just wondering why you don't use the solution from house robber to solve this problem?
You are one heck of a problem solver and on top of that a great explainer. Cheers friend!
C++ code:
int n=cost.size();
int dp[n+2];
dp[n+1]=0;dp[n]=0;
int jumpCost1,jumpCost2;
for(int i=n-1;i>=0;i--){
jumpCost1=cost[i]+dp[i+1];
jumpCost2=cost[i]+dp[i+2];
dp[i]=min(jumpCost1,jumpCost2);
}
return min(dp[0],dp[1]);
Brilliant !
U R the BEST!!
It's weird that the problem is called "climbing stairs".
I mean, what stairs have one step being 100 times more expensive to climb that the previous one?
Why didn't they call the problem "saving fuel on an airplane" or something.
My god you're amazing
you're the best
Beautiful
nice one
This is just reverse greedy in a way. !! It not even seems like DP
great content keep doing & make explaination easier
7:58
Easier problem explained in a difficult way.
your brute force solution misses the fact that we can start at either position 0 or position 1, we can run two seperate stack traces from each poisiton and get the min, or we can start jumping from position -1. the cost there is 0, and it can either jump to position 0 or position 1.
my bruteforce code:
def minCostClimbingStairs(self, cost: List[int]) -> int:
minC = 10000000000000
def jump(n, c, minC):
if n >= len(cost):
minC = min(minC, c)
return minC
if n > -1:
c += cost[n]
return min(jump(n + 1, c, minC), jump(n + 2, c, minC))
return jump(-1, 0, minC)
great
Is it just me that prefers the recursive solution to this?
You lost me with Python. I mostly followed along up until then.
yea you fucked up this explanation
Quite misleading explanation
would be nice to cut down long explanation, need to say what needs to be said concisely avoiding tiring wordiness.
eh i think its useful
Facebook, whatsapp, Instagram down
yooo actually i was wondering what tf was up and why i couldn't dm my mate
at least leetcode is still up lol..
I do believe that we dont need the line of "cost.append(0)" , I just removed it , and still works
Thanks!