หาต้นทุนน้อยที่สุดปีนบันไดถึงปลายด้วยการกระโดดสูงสุด k ขั้นใน Python

มีลิสต์ stairs ค่าแต่ละขั้น = ต้นทุน เริ่มขั้น 0 ต้องไปขั้นสุดท้าย กระโดดได้ 1..k ขั้นต่อครั้ง หาต้นทุนรวมน้อยที่สุด

ตัวอย่าง: stairs = [4, 11, 11, 3, 2], k = 3 → 9 (ทาง: 4 → 3 → 2)

แนวทาง (Sliding Window Minimum ด้วย Deque)

1. ใช้ Deque เก็บคู่ (cost, index) เรียง cost น้อยไปมาก
2. สำหรับแต่ละขั้น i:
• ลบข้างหน้าที่เกินระยะ k
• curcost = deque[0].cost + stairs[i]
• ลบข้างหลังที่ cost ≥ curcost
• เพิ่ม (curcost, i) เข้า deque
3. คำตอบ = cost ของขั้นสุดท้ายใน deque

ตัวอย่างโค้ด

from collections import deque

class Solution:
    def solve(self, stairs, k):
        q = deque([(stairs[0], 0)])
        for i in range(1, len(stairs)):
            while i - q[0][1] > k:
                q.popleft()
            curcost = q[0][0] + stairs[i]
            while q and curcost <= q[-1][0]:
                q.pop()
            q.append((curcost, i))
        return q[-1][0]

ob = Solution()
stairs = [4, 11, 11, 3, 2]
k = 3
print(ob.solve(stairs, k))  # 9

อินพุต

[4, 11, 11, 3, 2], 3

เอาต์พุต

9