解题思路

  1. 使用 数组记录到达每个位置能获得的最大积分
  2. 对于每个位置 ，遍历其能跳到的所有位置
  3. 状态转移方程：
  4. 需要先判断位置是否可达，使用一个布尔数组记录可达性
  5. 最后检查终点是否可达，如果可达则返回 ，否则返回

代码

#include <iostream>
#include <vector>
using namespace std;

int maxScore(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) return -1;
    if (n == 1) return nums[0];
    
    vector<bool> can_reach(n, false);  // 记录位置是否可达
    vector<int> dp(n, 0);  // 记录到达每个位置的最大积分
    
    can_reach[0] = true;
    dp[0] = nums[0];
    
    // 遍历每个位置
    for (int i = 0; i < n; i++) {
        if (!can_reach[i]) continue;
        
        // 从当前位置能跳到的所有位置
        for (int j = i + 1; j <= min(i + nums[i], n - 1); j++) {
            can_reach[j] = true;
            dp[j] = max(dp[j], dp[i] + nums[j]);
        }
    }
    
    return can_reach[n-1] ? dp[n-1] : -1;
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    
    cout << maxScore(nums) << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static int maxScore(int[] nums) {
        int n = nums.length;
        if (n == 0) return -1;
        if (n == 1) return nums[0];
        
        boolean[] canReach = new boolean[n];
        int[] dp = new int[n];
        
        canReach[0] = true;
        dp[0] = nums[0];
        
        for (int i = 0; i < n; i++) {
            if (!canReach[i]) continue;
            
            for (int j = i + 1; j <= Math.min(i + nums[i], n - 1); j++) {
                canReach[j] = true;
                dp[j] = Math.max(dp[j], dp[i] + nums[j]);
            }
        }
        
        return canReach[n-1] ? dp[n-1] : -1;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        
        System.out.println(maxScore(nums));
    }
}

def maxScore(nums):
    n = len(nums)
    if n == 0:
        return -1
    if n == 1:
        return nums[0]
    
    can_reach = [False] * n  # 记录位置是否可达
    dp = [0] * n  # 记录到达每个位置的最大积分
    
    can_reach[0] = True
    dp[0] = nums[0]
    
    # 遍历每个位置
    for i in range(n):
        if not can_reach[i]:
            continue
            
        # 从当前位置能跳到的所有位置
        for j in range(i + 1, min(i + nums[i] + 1, n)):
            can_reach[j] = True
            dp[j] = max(dp[j], dp[i] + nums[j])
    
    return dp[n-1] if can_reach[n-1] else -1

n = int(input())
nums = list(map(int, input().split()))
print(maxScore(nums))

算法及复杂度

  • 算法：动态规划
  • 时间复杂度： - 对于每个位置都可能需要遍历后面的所有位置
  • 空间复杂度： - 需要两个长度为n的数组

这道题是跳跃游戏的变体，除了要判断能否到达终点外，还需要计算最大积分。关键点在于：

  1. 需要同时维护两个数组：

    • 数组记录每个位置是否可达
    • 数组记录到达每个位置的最大积分

  2. 状态转移的过程：

    • 只有当前位置 可达时才进行跳跃
    • 对于可以跳到的每个位置 ，更新其可达性和最大积分
    • 最大积分的更新公式：

  3. 特殊情况处理：

    • 数组长度为 时返回
    • 数组长度为 时直接返回
    • 如果终点不可达，返回

这种方法能够保证找到所有可能的跳跃路径，并在其中选择积分最大的一条。