871. Minimum Number of Refueling Stops - Day 20/31 Leetcode August Challenge

Larry solves and analyzes this Leetcode problem as both an interviewer and an interviewee. This is a live recording of a real engineer solving a problem live - no cuts or edits!
Problem: leetcode.com/p...
Twitch: / larryny
Discord: / discord
Instagram: / larrysomewhere
#leetcode #coding #programming

[@Algorithmist]

Did you fuel your way through this problem?

[@VasheshJ]

Enough fuel to reach the destination !!

[@codeandchill6623]

Hey Larry. What resources do you recommend to practice similar dp problems. I was trying to do it like knapsack and I am not the most comfortable with non-recursive DP . I would love to hear from you how we can really master this topic.
BTW HERE"s my CODE (passed 103 cases)
class Solution:
def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
if(startFuel >=target):return 0

@lru_cache(maxsize=None)
def dfs(fuelLeft,index):
if(fuelLeft >= target):
return 0
elif(index >= len(stations)):
return inf
elif(fuelLeft < stations[index][0]):
return inf
else:
a = 1 + dfs(fuelLeft+ stations[index][1],index+1)
b = dfs(fuelLeft,index+1)

return min(a,b)

t = dfs(startFuel,0)
return -1 if t == inf else t

[@Algorithmist]

@@codeandchill6623 I think LC has a bunch of them, it really is just practice!

[@amrhassan9181]

I'm really impressed with the amount of problems you solved, can't help it but admire your commitment,
Tho to be honest for me it's hard to understand most of your solutions from the first look, I always need to experiment a bit try to see how each stage function so if you could explain your solution a bit more as well as using some visuals, it will help me a lot as well as many more people.
Thanks for your content & time Larry.

[@Algorithmist]

Ya this one is a little harder - as I stated in the beginning I am solving/working on this problem and was not certain of its correctness yet.

[@cholocatelabs]

this is tricky, !!

[@codeandchill6623]

Hey Larry. What resources do you recommend to practice similar dp problems. I was trying to do it like knapsack and I am not the most comfortable with non-recursive DP . I would love to hear from you how we can really master this topic.
BTW HERE"s my CODE (passed 103 cases)
class Solution:
def minRefuelStops(self, target: int, startFuel: int, stations: List[List[int]]) -> int:
if(startFuel >=target):return 0
@lru_cache(maxsize=None)
def dfs(fuelLeft,index):
if(fuelLeft >= target):
return 0
elif(index >= len(stations)):
return inf
elif(fuelLeft < stations[index][0]):
return inf
else:
a = 1 + dfs(fuelLeft+ stations[index][1],index+1)
b = dfs(fuelLeft,index+1)
return min(a,b)
t = dfs(startFuel,0)
return -1 if t == inf else t

[@alienx2367]

Dude at least use digital whiteboard or something to explain your approach -_-