หา Cost ต่ำสุดไปถึง Index สุดท้าย ก้าวได้สูงสุด k Steps (DP + Min Heap) ใน Python

ปัญหา: Array `nums[i]` = Cost ของการยืนที่ Index i เริ่ม Index 0 จบ Index n-1 แต่ละ Step ก้าวได้ 1..k Steps หา Min Total Cost

อัลกอริทึม: DP + Monotonic Min-Heap (Sliding Window Minimum)

DP[i] = Min Cost ถึง Index i = nums[i] + min(DP[i-k], ..., DP[i-1])

ใช้ Min-Heap เก็บ `(dp_value, index)` สำหรับ Sliding Window Size k

การติดตั้ง

from heapq import heappush, heappop

class Solution:
    def solve(self, nums, k):
        n = len(nums)
        dp = [0] * n
        heap = []  # (dp_value, index)
        
        for i in range(n):
            # Remove Expired Indices (Out of Window k)
            while heap and heap[0][1] < i - k:
                heappop(heap)
            
            # Min DP in Window
            min_prev = heap[0][0] if heap else 0
            
            dp[i] = nums[i] + min_prev
            heappush(heap, (dp[i], i))
        
        return dp[-1]

# Test
ob = Solution()
nums = [2, 3, 4, 5, 6]
k = 2
print(ob.solve(nums, k))  # 12 (Path: 0→2→4: 2+4+6=12)

คำอธิบาย

• `dp[i]` = Min Cost ถึง i

• Heap เก็บ `(dp[j], j)` สำหรับ j ใน `[i-k, i-1]`

• ก่อนคำนวณ `dp[i]`: Pop Heap จน Index ≥ i-k (In Window)

• `min_prev = heap[0][0]` = Min DP ใน Window (Heap Property)

• Push `(dp[i], i)` เข้า Heap สำหรับ Future Windows

Trace: nums=[2,3,4,5,6], k=2

i=0: heap=[] → min_prev=0 → dp[0]=2+0=2 → heap=[(2,0)]
i=1: heap=[(2,0)] (0 ≥ -1) → min_prev=2 → dp[1]=3+2=5 → heap=[(2,0),(5,1)]
i=2: heap=[(2,0),(5,1)] (0 ≥ 0) → min_prev=2 → dp[2]=4+2=6 → heap=[(2,0),(5,1),(6,2)]
i=3: Pop (2,0) (0 < 1) → heap=[(5,1),(6,2)] → min_prev=5 → dp[3]=5+5=10 → heap=[(5,1),(6,2),(10,3)]
i=4: Pop (5,1) (1 < 2) → heap=[(6,2),(10,3)] → min_prev=6 → dp[4]=6+6=12 → heap=[(6,2),(10,3),(12,4)]
Answer: dp[4]=12
Path: 0→2→4 (2+4+6=12) หรือ 0→1→3→4? No, k=2 max step.

Complexity

• Time: O(n log k) - แต่ละ Element Push/Pop Heap Max 1 ครั้ง
• Space: O(k) - Heap Size ≤ k

Alternative: Deque (Monotonic Queue) O(n)

from collections import deque

def solve_deque(nums, k):
    n = len(nums)
    dp = [0] * n
    dq = deque()  # Indices with Increasing dp Values
    
    for i in range(n):
        # Remove Out of Window
        while dq and dq[0] < i - k:
            dq.popleft()
        
        min_prev = dp[dq[0]] if dq else 0
        dp[i] = nums[i] + min_prev
        
        # Maintain Monotonic Increasing
        while dq and dp[dq[-1]] >= dp[i]:
            dq.pop()
        dq.append(i)
    
    return dp[-1]

Variations

• ก้าวได้ 1..k Steps (Variable) → Same
• ก้าวได้ Specific Steps Set → Check Each
• 2D Grid Version → Dijkstra/DP