Skip to content

Instantly share code, notes, and snippets.

@thmain
Last active October 27, 2023 01:20
Show Gist options
  • Save thmain/a139ea000f64b054a0c97142531ab104 to your computer and use it in GitHub Desktop.
Save thmain/a139ea000f64b054a0c97142531ab104 to your computer and use it in GitHub Desktop.
class MinimumCostStaircaseRecursion:
def minCost(self, cost):
stairs = len(cost) - 1
return self.util(cost, -1, stairs)
def util(self, cost, current, stairs):
if current == stairs:
return cost[current]
if current > stairs:
return 0
cst = cost[current] if current >= 0 else 0 # pay the cost at this stair
minimum = min(
self.util(cost, current + 1, stairs),
self.util(cost, current + 2, stairs)
)
return cst + minimum
if __name__ == "__main__":
m = MinimumCostStaircaseRecursion()
costs = [10, 1, 1, 15, 2, 30, 3]
print("minimum cost:", m.minCost(costs))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment