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!
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.
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)
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.
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
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
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.
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
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.
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.
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)
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])
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])
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); } return min(dp[0],dp[1]);
