Jump Game

描述

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:

A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

分析

由于每层最多可以跳A[i]步，也可以跳0或1步，因此如果能到达最高层，则说明每一层都可以到达。有了这个条件，说明可以用贪心法。

思路一：正向，从0出发，一层一层网上跳，看最后能不能超过最高层，能超过，说明能到达，否则不能到达。

思路二：逆向，从最高层下楼梯，一层一层下降，看最后能不能下降到第0层。

思路三：如果不敢用贪心，可以用动规，设状态为f[i]，表示从第0层出发，走到A[i]时剩余的最大步数，则状态转移方程为：

f[i]=max(f[i−1],A[i−1])−1,i>0f[i] = max(f[i-1], A[i-1])-1, i > 0

代码1

  1. // Jump Game
  2. // 思路1，时间复杂度O(n)，空间复杂度O(1)
  3. public class Solution {
  4.     public boolean canJump(int[] nums) {
  5.         int reach = 1; // 最右能跳到哪里
  6.         for (int i = 0; i < reach && reach < nums.length; ++i)
  7.             reach = Math.max(reach,  i + 1 + nums[i]);
  8.         return reach >= nums.length;
  9.     }
  10. }

代码2

  1. // Jump Game
  2. // 思路2，时间复杂度O(n)，空间复杂度O(1)
  3. public class Solution {
  4.     public boolean canJump(int[] nums) {
  5.         if (nums.length == 0) return true;
  6.         // 逆向下楼梯，最左能下降到第几层
  7.         int left_most = nums.length - 1;
  9.         for (int i = nums.length - 2; i >= 0; --i)
  10.             if (i + nums[i] >= left_most)
  11.                 left_most = i;
  13.         return left_most == 0;
  14.     }
  15. }

代码3

  1. // Jump Game
  2. // 思路三，动规，时间复杂度O(n)，空间复杂度O(n)
  3. public class Solution {
  4.     public boolean canJump(int[] nums) {
  5.         int[] f = new int[nums.length];
  6.         for (int i = 1; i < nums.length; i++) {
  7.             f[i] = Math.max(f[i - 1], nums[i - 1]) - 1;
  8.             if (f[i] < 0) return false;;
  9.         }
  10.         return f[nums.length - 1] >= 0;
  11.     }
  12. }

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/greedy/jump-game.html