Jump Game解题报告

Description:

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.

Link:

http://www.lintcode.com/en/problem/jump-game/

题目意思：

给出一个数组，每个位置的值表示从此处位置可以向后跳几步，判断能否跳到最后一步。

解题方法：

解法1：DP
创建一个size为n的bool数组dp，表示每个位置是否能跳到。从1到n-1位置分别从后(从i-1)向前查(到0)找以判断i位置能否到达，判断方程为：dp[j] && A[j] >= i-j。如果可以，则将dp[i]设为true，否则为false;

解法2：greedy
思想很简单，从前往后遍历数组，记录当前能跳到的最远位置int far，当有在far之前的位置(i <= far)能够跳到比far还远的时候(A[i] + i >= far)，就更新far，最后比较far和终点的远近。

Tips:

使用DP解法时可能会超时，但是当出现一个false时就可以直接返回false，因为当终点前一步都不能走到时，终点当然也不可能走到。

Time Complexity：

DP: O(N^2)
Greedy: O(N)

完整代码：

DP
bool canJump(vector<int> A) { vector<bool> reach(A.size(), false); reach[0] = true; for(int i = 1; i < A.size(); i++) { for(int j = i-1; j >= 0; j--) { if(reach[j] && A[j] >= i-j) { reach[i] = true; break; } } if(!reach[i]) return false; } return reach[A.size() - 1];
Greedy
bool canJump(vector<int> A) { if(A.size() == 0) return false; int far = A[0]; for(int i = 1; i < A.size(); i++) if(i <= far && A[i] + i >= far) far = A[i] + i; return far >= A.size() - 1; }