파이썬에서 점프 게임에서 얻을 수 있는 최대 점수를 찾는 프로그램

nums라는 배열과 다른 값 k가 있다고 가정합니다. 우리는 인덱스 0에 있습니다. 한 번의 이동으로 배열의 경계를 벗어나지 않고 최대 k 단계 오른쪽으로 이동할 수 있습니다. 배열의 최종 인덱스에 도달하고 싶습니다. 점프를 위해 우리는 점수를 얻습니다. 이것은 배열에서 방문한 각 인덱스 j에 대한 모든 nums[j]의 합입니다. 얻을 수 있는 최대 점수를 찾아야 합니다.

따라서 입력이 nums =[1,-2,-5,7,-6,4] k =2와 같으면 출력은 10이 됩니다. 왜냐하면 이 시퀀스 [1, -2, 7, 4] 그러면 최대 점수가 10점이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• n :=숫자 크기
• 점수 :=크기가 n이고 0으로 채워진 배열
• 점수[0] :=숫자[0]
• currMax :=점수[0]
• max_pt :=0
• n <1이면
  • 0을 반환
• n이 1과 같으면
  • 숫자의 마지막 요소 반환
• 1 ~ n - 1 범위의 idx에 대해
  • max_pt>=idx - k인 경우
    • currMax <점수[idx-1]이고 idx> 0이면
      • currMax :=점수[idx-1]
      • max_pt :=idx-1
  • 그렇지 않으면
    • idx - k> 0이면
      • currMax :=점수[idx-k]
      • max_pt :=idx - k
      • idx-k ~ idx 범위의 p에 대해
        • 점수[p]>=currMax이면
          • max_pt :=p
          • currMax :=점수[p]
  • 점수[idx] :=currMax + 숫자[idx]
• 점수의 마지막 요소:=currMax + nums[-1]
• 점수의 마지막 요소 반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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))

입력

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

출력

10