สมมติว่ามีบันได ขั้นตอน i-th จะกำหนดต้นทุนมูลค่าต้นทุนที่ไม่เป็นลบ[i] เมื่อเราจ่ายค่าใช้จ่าย เราสามารถปีนขึ้นได้หนึ่งหรือสองขั้น เราต้องหาต้นทุนขั้นต่ำเพื่อไปให้ถึงชั้นบนสุด และเรายังสามารถเริ่มจากขั้นตอนที่มีดัชนี 0 หรือขั้นตอนที่มีดัชนี 1
ดังนั้น หากอินพุตมีค่าเท่ากับ cost =[12,17,20] ผลลัพธ์จะเป็น 17 ซึ่งเป็นตำแหน่งที่ถูกที่สุดในการเริ่มต้นจากขั้นตอนที่ 1 เนื่องจากเราต้องจ่ายค่าใช้จ่ายนั้นและไปที่ด้านบนสุด
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- dp :=อาร์เรย์ที่มีขนาดเท่ากับราคา และเติมด้วย 0
- dp[0] :=cost[0]
- ถ้าขนาดของต้นทุน>=2 แล้ว
- dp[1] :=ราคา[1]
- สำหรับ i ในช่วง 2 ถึงขนาดของต้นทุน - 1 ทำ
- dp[i] :=cost[i] + ขั้นต่ำ dp[i-1], dp[i-2]
- ส่งคืนขั้นต่ำ dp[-1], dp[-2]
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution: def minCostClimbingStairs(self, cost): dp = [0] * len(cost) dp[0] = cost[0] if len(cost) >= 2: dp[1] = cost[1] for i in range(2, len(cost)): 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]))
อินพุต
[12,17,20]
ผลลัพธ์
17
