10/12 每日一題(動態規劃計算最小成本)

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.

 class Solution:

    def minCostClimbingStairs(self, cost: List[int]) -> int:

        n=len(cost)

        dp=[0]*(n+1)

        #n+1 考慮到頂樓的情況

        for i in range(2,n+1):

            dp[i]=min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1])

            #比較跳2步和跳一步的代價

            #並且將結果記錄到list中

        print(dp)

        return min(dp[-1],dp[-2]+cost[-1])

        #比較最後兩種跳法的代價

------------------------

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        if len(cost)==1: return cost[0]

        dp=[0 for _ in range(len(cost))]
        dp[0]=cost[0]
        dp[1]=cost[1]

#用來存每一層的最小代價

        for i in range(2, len(cost)):
            dp[i]=cost[i]+min(dp[i-1],dp[i-2])

#考慮地i樓的成本是前一樓跳上來或是前兩樓跳上來低
        
        return min(dp[-1], dp[-2])

#回傳前一樓跳或是前兩樓跳