Python 中查詢跳躍遊戲中最大分數的程式

假設我們有一個名為 nums 的陣列和另一個值 k。我們位於索引 0。一步之內，我們可以最多跳躍 k 步到右邊，而不會超出陣列的邊界。我們希望到達陣列的最終索引。對於跳躍，我們獲得分數，即我們訪問的陣列中每個索引 j 的所有 nums[j] 的總和。我們必須找到我們可以獲得的最大分數。

因此，如果輸入類似於 nums = [1,-2,-5,7,-6,4] k = 2，則輸出將為 10，因為我們按照此順序跳躍 [1, -2, 7, 4]，然後我們將獲得最大分數，即 10。

為了解決這個問題，我們將遵循以下步驟：

  • n := nums 的大小
  • scores := 一個大小為 n 且填充為 0 的陣列
  • scores[0] := nums[0]
  • currMax := scores[0]
  • max_pt := 0
  • 如果 n < 1，則
    • 返回 0
  • 如果 n 等於 1，則
    • 返回 nums 的最後一個元素
  • 對於 idx 從 1 到 n - 1 的範圍，執行以下操作：
    • 如果 max_pt >= idx - k，則
      • 如果 currMax < scores[idx-1] 且 idx > 0，則
        • currMax := scores[idx-1]
        • max_pt := idx-1
    • 否則，
      • 如果 idx - k > 0，則
        • currMax := scores[idx-k]
        • max_pt := idx - k
        • 對於 p 從 idx-k 到 idx 的範圍，執行以下操作：
          • 如果 scores[p] >= currMax，則
            • max_pt := p
            • currMax := scores[p]
    • scores[idx] := currMax + nums[idx]
  • scores 的最後一個元素 := currMax + nums[-1]
  • 返回 scores 的最後一個元素

示例

讓我們看看以下實現以更好地理解：

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

更新於: 2021年10月6日

574 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告