题解 | #跳跃游戏(一)# Python3
跳跃游戏(一)
https://www.nowcoder.com/practice/07484f4377344d3590045a095910992b
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
# 因此，可以采用贪心策略，从后往前遍历数组，迭代看当前位置+值能否到达目的位置，可以的话，只需要到达当前位置
# 就可以到达最后的目的位置
查看34道真题和解析
别扯什么自己这那的 我感觉领导确实已经给你很多时间和空间了 自己还是想想有没有真的用心去做 不是什么东西都要别人推着你去干的 总得学会主动一点吧 最后中肯地说一句 卷不了还是别走互联网这条路了 不好意思说话有些直白但希望你可以明白我的意思