题解 | #跳跃游戏(二)#
跳跃游戏(二)
https://www.nowcoder.com/practice/58e31b785f4b4ced9695dd4fcd60c1ce
python3
前向DP版本，时间复杂度O(n2)比倒推法O(n)要高，但可以通过测试。
def solution(n,nums): if not n: return -1 maxL = nums[0] dp = [nums[i] for i in range(n)] #以nums[i]为结尾的序列所能获得的maxVal for i in range(1,n): #1)从nums[0:i)不能到达第i个位置，即当前所能到达的 maxL < i，则无法跳到终点。 #2)maxL >= i, 则从nums[0:i)某个位置一定能跳到位置i if maxL < i: return -1 maxL = max(maxL, i+nums[i])#更新maxL #往回寻找能跳到位置i的最大值位置 j = i-1 #目标位置就是距离位置 i 最近且能到达位置 i 的位置！！ #假设有且只有k,j都能到达 i，且 k < j < i。则最优解只可能是由k跳到j,再由j跳到i。因为nums值都>=0。 while(nums[j] + j < i): j -= 1 #更新以位置i为结尾的序列的maxVal dp[i] = max(dp[i],nums[i]+dp[j]) return dp[-1] if __name__ == "__main__": n = int(input()) data = list(map(int,input().split())) res = solution(n,data) print(res)
左边刷题右边 chat 效果很好