Min Cost Climbing Stairs - Dynamic Programming - Leetcode 746 - Python

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

#coding #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[bryan_txg]

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...

[chaitanyavarma]

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!

[letscode]

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:])

[hyperboliq]

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.

[resa_uyi]

You are an asset to the programming world. Thank you.

[nero]

Are DP questions really common on interviews? I feel like only Google would ask them, I got asked House Robber on their phone screen.

[pshr]

your channel is like a gift from God ngl

[ThethProgrammer]

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.

[shubhammishra]

After explanation without watching coding part I solved this. Nice explanation.

[alexm]

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.

[hassan]

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.

[aboudithebault]

Dude just... thanks. You are Abdul Bari level

[atg]

no one literally takes me through the dp this level except you, thank you 🤞🤞🤞🤞🤞🤞🤞🤞

[TheSimilarBoy]

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)

[sushilkhadka]

You are a gift from god. Regretting why didn't I find you before

[alasdairmacintyre]

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

[shamsularefinsajib]

This IS NOT an EASY problem for everyone!! should be marked as MEDIUM

[andriidilai]

thanks for the video!
looks like we can skip adding trailing zero. this code works as well:

class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
for i in range(len(cost)-3, -1, -1):
cost[i] += min(cost[i+1], cost[i+2])
return min(cost[0], cost[1])

[whonayem]

Thanks.

I think we don't need to add 0 at the end since the cost can't be negative.

[apriil]

NeetCode: yeah, that's the entire code...
Me: magic!!!