MinimumCostStaircaseRecursion.py

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