# Jump Game

## Question

• lintcode:

(116) 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.

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

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


## 题解(自顶向下-动态规划)

1. State: f[i] 从起点出发能否达到i
2. Function: f[i] = OR (f[j], j < i ~\&\&~ j + A[j] \geq i), 状态 $j$ 转移到 $i$, 所有小于i的下标j的元素中是否存在能从j跳转到i得
3. Initialization: f[0] = true;
4. Answer: 递推到第 N - 1 个元素时，f[N-1]

### C++ from top to bottom

class Solution {
public:
/**
* @param A: A list of integers
*/
bool canJump(vector<int> A) {
if (A.empty()) {
return true;
}

vector<bool> jumpto(A.size(), false);
jumpto[0] = true;

for (int i = 1; i != A.size(); ++i) {
for (int j = i - 1; j >= 0; --j) {
if (jumpto[j] && (j + A[j] >= i)) {
jumpto[i] = true;
break;
}
}
}

return jumpto[A.size() - 1];
}
};


## 题解(自底向上-贪心法)

1. State: f[i] 从 $i$ 出发能否到达最终位置
2. Function: $f[j] = j + A[j] \geq i$, 状态 $j$ 转移到 $i$, 置为true
3. Initialization: 第一个为true的元素为 A.size() - 1
4. Answer: 递推到第 0 个元素时，若其值为true返回true

### C++ greedy, from bottom to top

class Solution {
public:
/**
* @param A: A list of integers
*/
bool canJump(vector<int> A) {
if (A.empty()) {
return true;
}

int index_true = A.size() - 1;
for (int i = A.size() - 1; i >= 0; --i) {
if (i + A[i] >= index_true) {
index_true = i;
}
}

return 0 == index_true ? true : false;
}
};


## 题解(自顶向下-贪心法)

### C++ greedy, from top to bottom

class Solution {
public:
/**
* @param A: A list of integers
*/
bool canJump(vector<int> A) {
if (A.empty()) {
return true;
}

int farthest = A[0];

for (int i = 1; i != A.size(); ++i) {
if ((i <= farthest) && (i + A[i] > farthest)) {
farthest = i + A[i];
}
}

return farthest >= A.size() - 1;
}
};