Min Cost Climbing Stairs - Dynamic Programming - Leetcode 746 - Python
Vložit
- čas přidán 28. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
📚 STACK PLAYLIST: • Stack Problems
Problem Link: neetcode.io/problems/min-cost...
0:00 - Read the problem
4:00 - Drawing Brute Force
6:32 - Drawing Memoization
10:40 - Drawing Dynamic Programming
16:02 - Coding DP Solution
leetcode 746
This question was identified as a google interview question from here: github.com/xizhengszhang/Leet...
#coding #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
💡 DYNAMIC PROGRAMMING PLAYLIST: czcams.com/video/73r3KWiEvyk/video.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
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.
thank you so much for providing such beautiful solutions!
no one literally takes me through the dp this level except you ,thank you 🤞🤞🤞🤞🤞🤞🤞🤞
Great Explanation Thanks!!!
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)
Your videos are my best find on the way to my dream!
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.
You are a gift from god. Regretting why didn't I find you before
Thanks.
I think we don't need to add 0 at the end since the cost can't be negative.
thank you for walking through your thought process! only wish you were a java programmer... : )
Thanks!
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
NeetCode: yeah, that's the entire code...
Me: magic!!!
Simply the Best!
This IS NOT an EASY problem for everyone!! should be marked as MEDIUM
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.
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
U R the BEST!!
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.
Great video
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.
Brilliant !
I liked the explanation
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]);
Maza aa raha hai dil garden garden ho raha hai ek bar mein 3eno se solve Kar liya
for i in range(2,len(cost)):
cost[i]+=min(cost[i-1],cost[i-2])
return min(cost[-1],cost[-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)
great content keep doing & make explaination easier
nice one
craziest part, you dont even need to go reverse order
you're 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?
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])
Beautiful
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.
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))
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!
great
This is just reverse greedy in a way. !! It not even seems like DP
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])
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)
Is it just me that prefers the recursive solution to this?
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!