题解 | #跳跃游戏(二)# Python3

from sre_compile import BRANCH
import sys

# 17:57

# 方法一 :dp[i] 为 到 i的最大积分, O(MN), 超时
# dp[i] = max(j从0到i-1过程中，满足nums[i] > i-j，dp[j]+nums[i])

n = int(input())

if n == 0: 
    print(-1)
else:
    # flag = True
    # nums = list(map(int,input().strip().split()))
    # dp = [0]* n
    # for i in range(1,n):
    #     for j in range(i):
    #         if nums[j] >= i-j:
    #             dp[i] = max(dp[i],dp[j]+nums[j])
    #     if dp[i] == 0: #本格无法到达, 直接break and false
    #         flag = False
    #         break
    # if flag:
    #     print(dp[-1]+ nums[-1])
    # else:
    #     print(-1)

    # 方法二: 其实就是选那条最长的路径，把所有到达终点能走的都走了
    # 假设从倒数最后一步到终点，有多种跳跃，
    # 那么最长跳跃到终点的那个，除了可以跳跃到终点，也可以跳跃到其他可以一步跳跃到终点的格子
    # 因此，就是遍历买个可以踩的点，最长序列
    # 因此直接使用贪心+回溯
    nums = list(map(int,input().strip().split()))
    max_score = 0
    target_idx = n - 1
    for i in range(n-1,-1,-1):
        if nums[i] >= target_idx-i:
            max_score += nums[i]
            target_idx = i

    if target_idx !=0:
        print(-1)
    else:
        print(max_score)