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

import sys


# 方法一： O(NN)，超时
# dp[i] = 能否跳到i
# dp[i] = (j从0~i-1, dp[j]==1 & nums[j]>= (i-j))

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

# dp = [False] * (n)
# dp[0] = True



# for i in range(1,n):
#     for j in range(i):
#         if dp[j] and nums[j] >= (i-j):
#             dp[i] = True
#             break

# print('true' if dp[-1] else 'false')

# 方法二， dp[i]为在i还能跳往后到达多少格，
# 如何dp[i]==0，说明无法再向后跳了
# dp[i] = max(dp[i-1]-1,nums[i])
# dp[i]
dp = [0] * (n+1)
flag = True
for i in range(1,n+1):
    dp[i] = max(dp[i-1]-1, nums[i-1])
    if dp[i] == 0 and i!=n: # 最后一个不需要往后跳，已经到达
        flag = False
        break
print('true' if flag else 'false')

# 方法三，注意，如果能到达i，一定能到达i-1
# 因此，可以采用贪心策略，从后往前遍历数组，迭代看当前位置+值能否到达目的位置，可以的话，只需要到达当前位置
# 就可以到达最后的目的位置