在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的大小
分数：大小为n的数组，填充为0
分数[0]：nums [0]
currMax：分数[0]
max_pt：0
如果n <1，则
- 返回0
如果n与1相同，则
- 返回nums的最后一个元素
对于范围为1到n-1的idx，执行以下操作
- 如果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
  - 对于范围为idx-k到idx的p，执行
    - 如果scores[p]≥currMax，则
    - max_pt：= p
    - currMax：= scores [p]
- 分数[idx]：= currMax + nums[idx]
分数的最后一个元素：= 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))