-
Notifications
You must be signed in to change notification settings - Fork 0
/
746.py
40 lines (36 loc) · 1.29 KB
/
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
# 746. Min Cost Climbing Stairs
# On a staircase,
# the i-th step has some non-negative cost cost[i] assigned (0 indexed).
#
# Once you pay the cost,
# you can either climb one or two steps.
# You need to find minimum cost to reach the top of the floor,
# and you can either start from the step with index 0,
# or the step with index 1.
#
# Example 1:
# Input: cost = [10, 15, 20]
# Output: 15
# Explanation: Cheapest is start on cost[1],
# pay that cost and go to the top.
# Example 2:
# Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
# Output: 6
# Explanation: Cheapest is start on cost[0],
# and only step on 1s, skipping cost[3].
# Note:
# cost will have a length in the range [2, 1000].
# Every cost[i] will be an integer in the range [0, 999].
from typing import List
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
dp = [0 for _ in range(len(cost) + 1)]
# You can start at first stair or second stair, so dp[0] and dp[1] is 0.
for i in range(2, len(cost) + 1):
dp[i] = min(cost[i - 2] + dp[i - 2], cost[i - 1] + dp[i - 1])
return dp[len(cost)]
if __name__ == '__main__':
from util import Test
t = Test(Solution().minCostClimbingStairs)
t.equal(15, [10, 15, 20])
t.equal(6, [1, 100, 1, 1, 1, 100, 1, 1, 100, 1])