Tìm chi phí tối thiểu leo đến cuối cầu thang trong Python

Cho list stairs (chi phí mỗi bậc) và k (nhảy tối đa k bậc/lượt). Từ bậc 0 đến bậc cuối, tìm chi phí tối thiểu.

Ví dụ: stairs = [4,11,11,3,2], k = 3 → 9 (đi 4→3→2).

Giải pháp: Monotonic queue (deque) tối ưu DP. dp[i] = stairs[i] + min(dp[j]) với i-k <= j < i. Deque giữ cặp (cost, index) tăng dần cost, loại bỏ index quá xa.

Ví dụ triển khai

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

Đầu vào

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

Đầu ra

9