题目大意:给一个数组,第i个位置的值表示当前可以往前走的最远距离,求从第一个位置能否顺利走到最后一个位置。例子如下:
法一(借鉴):DP,dp[i]表示从上一个位置走到当前位置时,剩余的可以往前走的距离。dp公式是:dp[i]=max(dp[i-1],nums[i-1])-1。代码如下(耗时5ms):
public boolean canJump(int[] nums) {
//dp[i]表示从上一个位置走到当前位置i时,还剩余的可往前走的步数是多少
int[] dp = new int[nums.length];
//dp[i] = max(dp[i- 1], nums[i - 1]) - 1
for(int i = 1; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1], nums[i - 1]) - 1;
if(dp[i] < 0) {
return false;
}
}
return true;
}
法二(借鉴):贪心,每次都更新记录当前能到达的最远距离,如果最远距离小于当前到达的位置或已到达终点,则break,更新最远距离,i+nums[i]表示当前能到达的最远距离。代码如下(耗时5ms):
public boolean canJump(int[] nums) {
int ma = 0;
for(int i = 0; i < nums.length; i++) {
//如果最远距离小于当前位置,表示当前位置不可达
if(i > ma || ma >= nums.length - 1) {
break;
}
//更新最远距离
ma = Math.max(ma, i + nums[i]);
}
return ma >= nums.length - 1;
}