55.Jump Game---dp

题目大意：给一个数组，第i个位置的值表示当前可以往前走的最远距离，求从第一个位置能否顺利走到最后一个位置。例子如下：

法一（借鉴）：DP，dp[i]表示从上一个位置走到当前位置时，剩余的可以往前走的距离。dp公式是：dp[i]=max(dp[i-1],nums[i-1])-1。代码如下（耗时5ms）：

 1     public boolean canJump(int[] nums) {
 2         //dp[i]表示从上一个位置走到当前位置i时，还剩余的可往前走的步数是多少
 3         int[] dp = new int[nums.length];
 4         //dp[i] = max(dp[i- 1], nums[i - 1]) - 1
 5         for(int i = 1; i < nums.length; i++) {
 6             dp[i] = Math.max(dp[i - 1], nums[i - 1]) - 1;
 7             if(dp[i] < 0) {
 8                 return false;
 9             }
10         }
11         return true;
12     }

View Code

法二（借鉴）：贪心，每次都更新记录当前能到达的最远距离，如果最远距离小于当前到达的位置或已到达终点，则break，更新最远距离，i+nums[i]表示当前能到达的最远距离。代码如下（耗时5ms）：

 1     public boolean canJump(int[] nums) {
 2         int ma = 0;
 3         for(int i = 0; i < nums.length; i++) {
 4             //如果最远距离小于当前位置，表示当前位置不可达
 5             if(i > ma || ma >= nums.length - 1) {
 6                 break;
 7             }
 8             //更新最远距离
 9             ma = Math.max(ma, i + nums[i]);
10         }
11         return ma >= nums.length - 1;
12     }

View Code