-
Notifications
You must be signed in to change notification settings - Fork 0
/
min-cost-climbing-stairs_746.py
40 lines (30 loc) · 1.26 KB
/
min-cost-climbing-stairs_746.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# You are given an integer array cost where cost[i] is the cost of ith step on a staircase.
# Once you pay the cost, you can either climb one or two steps.
# You can either start from the step with index 0, or the step with index 1.
# Return the minimum cost to reach the top of the floor.
# Example 1:
# Input: cost = [10,15,20]
# Output: 15
# Explanation: You will start at index 1.
# - Pay 15 and climb two steps to reach the top.
# The total cost is 15.
# Example 2:
# Input: cost = [1,100,1,1,1,100,1,1,100,1]
# Output: 6
# Explanation: You will start at index 0.
# - Pay 1 and climb two steps to reach index 2.
# - Pay 1 and climb two steps to reach index 4.
# - Pay 1 and climb two steps to reach index 6.
# - Pay 1 and climb one step to reach index 7.
# - Pay 1 and climb two steps to reach index 9.
# - Pay 1 and climb one step to reach the top.
# The total cost is 6.
# ---------------------------------------Runtime 69 ms Beats 41.86% Memory 16.4 MB Beats 43.70%---------------------------------------
# My solution
# Time complexity O(n)
from typing import List
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.pop(), cost.pop())