给出一个非负整数数组,你最初定位在数组的第一个位置。
数组中的每个元素代表你在那个位置可以跳跃的最大长度。
判断你是否能到达数组的最后一个位置。
样例
A =[2,3,1,1,4],返回 true.
A =[3,2,1,0,4],返回 false.
需要注意的是,例如你现在的位置是A[0],元素是2,你可以选择跳一位,也可以选择跳两位。两位便是你可以跳跃的最大长度。
此题可以使用动态规划来进行求解。
设置一个常量max_j,表示最远能到达的位置,遍历数组中每一个数字,如果当前坐标大于max_t或者max_t已经抵达最后一个位置则跳出循环,否则就更新max_t的值为其和i + A[i]中的较大值,其中i + A[i]表示当前位置能到达的最大位置
代码: