Min Cost Climbing Stairs ใน Python: หาต้นทุนต่ำสุดขึ้นบันได

มีบันไดแต่ละขั้นมีค่าใช้จ่าย cost[i] จ่ายค่าใช้จ่ายแล้วขึ้นได้ 1 หรือ 2 ขั้น เริ่มจากขั้น 0 หรือ 1 ก็ได้ หาต้นทุนรวมน้อยที่สุดถึงขั้นบนสุด (ด้านนอกอาร์เรย์)

ตัวอย่าง

cost = [12,17,20] → เริ่มขั้น 1 (จ่าย 17) ขึ้น 2 ขั้นถึงบนสุด → ต้นทุน 17

ขั้นตอนการแก้ปัญหา (Dynamic Programming)

1. dp[i] = ต้นทุนต่ำสุดถึงขั้น i
2. dp[0] = cost[0], dp[1] = cost[1]
3. dp[i] = cost[i] + min(dp[i-1], dp[i-2]) สำหรับ i >= 2
4. คำตอบ = min(dp[-1], dp[-2]) (เพราะจากขั้นสุดท้ายหรือลำดับก่อนหน้าขึ้นบนสุดได้)

การติดตั้งใน Python

class Solution:
    def minCostClimbingStairs(self, cost):
        n = len(cost)
        if n <= 1:
            return 0
        dp = [0] * n
        dp[0], dp[1] = cost[0], cost[1]
        for i in range(2, n):
            dp[i] = cost[i] + min(dp[i-1], dp[i-2])
        return min(dp[-1], dp[-2])

ob = Solution()
print(ob.minCostClimbingStairs([12, 17, 20]))  # 17

อินพุต / เอาต์พุต

Input: [12, 17, 20]
Output: 17