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.

Solutions:

1. DP1
每到一个点 i，我们扫描之前所有的点，如果之前某点j本身可达，并且与current 点可达，表示点i是可达的。

返回值：DP数组的最后一个值。

View Code

2. DP2
优化的点1：既然某点可达，肯定前面的点全部是可达的。这个比较好理解。因为你到达i点肯定要经过前面的一个点，这个依次推知可知前面所有的点可达。

所以我们不需要数组来记录结果，只要默认i点前全部可达就行了。

优化点2：如果某点不可达了，直接返回false。不需要再往后计算。

返回值：如果全部扫完仍没有返回false,返回true。

View Code

3. 递归
思想是，从前至尾扫描，至第一个距离与本点可达的点j，计算j点是否可达。使用递归计算j

点的可达性。

其实这里还是用到了贪心的思维。在考虑本点是否可达的时候，我们是考虑与本点最远的一个点是否可达。实际上这也make sense。

假设j点可以到达i点，那么后面的点可以不管。

（1）因为如果j点不可达，那么j+1也不可达。如果i不可达，后面的点也可不算。

（2）如果j点可达，并且j点可到达i,那么也没有必要再往后计算了。因为结论已经出来了。

  (3) 如果j点可达，但j不可达i，那么就继续计算。

View Code

4. GitHub代码

CanJump.java

References:

感谢http://blog.csdn.net/fightforyourdream/article/details/14219049给予的灵感。

LeetCode: Jump Game Total 解题报告