This page looks best with JavaScript enabled

Leetcode 746 Min Cost Climbing Stairs

題目大意

給一個整數 array, 在最多可連續跳過一個元素頭尾可被略過的條件下,加總被選取的整數:

Problem

https://leetcode.com/problems/min-cost-climbing-stairs/

My Solution

recursion

最先想到的是 recursion 作法

1
2
3
4
5
6
7
8
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        l = len(cost)
        if l is 1:
            return 0
        if l is 2:
            return min(cost)
        return min(cost[0]+self.minCostClimbingStairs(cost[1:]), cost[1]+self.minCostClimbingStairs(cost[2:]))

可是 TLE 了!

想想也對,因為明顯計算重疊到了

DP greedy + inplace

1
2
3
4
5
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        for i in range(2, len(cost)):
            cost[i] += min(cost[i-1], cost[i-2])
        return min(cost[-2:])