Jump Game

Jump Game

---

今天是一道有关贪婪算法的题目，来自LeetCode#55，难度为Medium，Acceptance为27.2%。

题目如下

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.

思路如下

该题中只需要求能不能到达最后一个元素，而不必求最少的步数，相对较为简单。只要按照贪婪算法，每到下一个元素求由该元素开始的最远的元素i + nums[i]即可。

代码如下

java版

public class Solution {
    public boolean canJump(int[] nums) {
        int reach = 0;
        for(int i = 0; i <= reach && reach < nums.length; i++) {
            reach = Math.max(reach, i + nums[i]);
        }
        return reach >= nums.length - 1;
    }
}

C++版

bool canJump(int A[], int n) {
    int i = 0;
    for (int reach = 0; i < n && i <= reach; ++i)
        reach = max(i + A[i], reach);
    return i == n;
}