Chương trình tìm điểm tối đa mà chúng ta có thể nhận được trong trò chơi nhảy bằng Python

Giả sử chúng ta có một mảng gọi là nums và một giá trị khác k. Chúng ta đang ở chỉ số 0. Trong một lần di chuyển, chúng ta có thể nhảy tối đa k bước sang phải mà không đi ra ngoài ranh giới của mảng. Chúng tôi muốn đạt đến chỉ mục cuối cùng của mảng. Đối với bước nhảy, chúng tôi nhận được điểm, đó là tổng của tất cả các num [j] cho mỗi chỉ số j mà chúng tôi đã truy cập trong mảng. Chúng ta phải tìm ra số điểm tối đa mà chúng ta có thể nhận được.

Vì vậy, nếu đầu vào giống như nums =[1, -2, -5,7, -6,4] k =2, thì đầu ra sẽ là 10 bởi vì, chúng ta nhảy trong chuỗi này [1, -2, 7, 4], sau đó chúng tôi sẽ nhận được điểm tối đa, và đó là 10.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của nums
• điểm số:=một mảng có kích thước n và được lấp đầy bởi 0
• điểm [0]:=nums [0]
• currMax:=điểm [0]
• max_pt:=0
• nếu n <1, thì
  • trả về 0
• nếu n giống 1, thì
  • trả về phần tử cuối cùng của nums
• đối với idx trong phạm vi từ 1 đến n - 1, thực hiện
  • nếu max_pt> =idx - k, thì
    • nếu currMax 0, thì
      • currMax:=Score [idx-1]
      • max_pt:=idx-1
  • nếu không,
    • nếu idx - k> 0, thì
      • currMax:=Score [idx-k]
      • max_pt:=idx - k
      • đối với p trong phạm vi idx-k đến idx, thực hiện
        • nếu điểm [p]> =currMax, thì
          • max_pt:=p
          • currMax:=Score [p]
  • điểm [idx]:=currMax + nums [idx]
• phần tử cuối cùng của điểm số:=currMax + nums [-1]
• trả về yếu tố cuối cùng của điểm số

Ví dụ

Hãy cùng chúng tôi xem cách 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