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.
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.
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.
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
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
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
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.
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.
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)
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])
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!
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])
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)
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); }
💡 DYNAMIC PROGRAMMING PLAYLIST: ua-cam.com/video/73r3KWiEvyk/v-deo.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!
You are an asset to the programming world. Thank you.
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?
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.
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
Are DP questions really common on interviews? I feel like only Google would ask them, I got asked House Robber on their phone screen.
your channel is like a gift from God ngl
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)
Dude just... thanks. You are Abdul Bari level
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.
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
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
After explanation without watching coding part I solved this. Nice explanation.
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
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.
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.
You are a gift from god. Regretting why didn't I find you before
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)
Thanks.
I think we don't need to add 0 at the end since the cost can't be negative.
no one literally takes me through the dp this level except you ,thank you 🤞🤞🤞🤞🤞🤞🤞🤞
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.
for i in range(2,len(cost)):
cost[i]+=min(cost[i-1],cost[i-2])
return min(cost[-1],cost[-2])
Thanks!
NeetCode: yeah, that's the entire code...
Me: magic!!!
Great Explanation Thanks!!!
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!
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])
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?
Maza aa raha hai dil garden garden ho raha hai ek bar mein 3eno se solve Kar liya
3:00 was my first exact thought lol
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])
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])
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))
thank you so much for providing such beautiful solutions!
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.
thank you for walking through your thought process! only wish you were a java programmer... : )
Your videos are my best find on the way to my dream!
Simply the Best!
craziest part, you dont even need to go reverse order
Brilliant !
Great video
I liked the explanation
Hi, I was just wondering why you don't use the solution from house robber to solve this problem?
U R the BEST!!
My god you're amazing
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)
nice one
Beautiful
you're the best
great
great content keep doing & make explaination easier
Is it just me that prefers the recursive solution to this?
This is just reverse greedy in a way. !! It not even seems like DP
Easier problem explained in a difficult way.
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]);
7:58
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!