Chương trình tìm điểm tối đa trong trò chơi nhảy trong Python

Cho mảng nums và giá trị k. Bắt đầu tại index 0. Mỗi bước nhảy tối đa k bước sang phải. Muốn đến cuối mảng. Điểm = tổng nums[j] các index đã ghé. Tìm điểm tối đa.

Ví dụ: nums = [1,-2,-5,7,-6,4], k = 2, đầu ra = 10 (nhảy theo [1, -2, 7, 4]).

Giải pháp

Dynamic Programming với tối ưu hóa sliding window maximum:

• n := len(nums), scores := mảng n phần tử 0
• scores[0] := nums[0], currMax := scores[0], max_pt := 0
• Nếu n < 1: trả về 0; nếu n == 1: trả về nums[-1]
• Với idx từ 1 đến n-1:
  • Nếu max_pt >= idx - k:
    • Nếu currMax < scores[idx-1] và idx > 0: currMax := scores[idx-1], max_pt := idx-1
  • Ngược lại:
    • Nếu idx - k > 0: currMax := scores[idx-k], max_pt := idx-k, tìm max trong [idx-k, idx)
  • scores[idx] := currMax + nums[idx]
• scores[-1] := currMax + nums[-1]
• Trả về scores[-1]

Ví dụ minh họa

Xem triển khai sau để hiểu rõ hơn:

def solve(nums, k):
    n = len(nums)
    scores = [0] * n
    scores[0] = nums[0]
    currMax = scores[0]
    max_pt = 0
    if n < 1:
        return 0
    if n == 1:
        return nums[-1]
    for idx in range(1, n):
        if max_pt >= idx - k:
            if currMax < scores[idx-1] and idx > 0:
                currMax = scores[idx-1]
                max_pt = idx-1
        else:
            if idx - k > 0:
                currMax = scores[idx-k]
                max_pt = idx - k
                for p in range(idx-k, idx):
                    if scores[p] >= currMax:
                        max_pt = p
                        currMax = scores[p]
        scores[idx] = currMax + nums[idx]
    scores[-1] = currMax + nums[-1]
    return scores[-1]

nums = [1,-2,-5,7,-6,4]
k = 2
print(solve(nums, k))

Đầu vào

[1,-2,-5,7,-6,4], 2

Đầu ra

10