# Leetcode No.55(Jump Game) 心得(Medium)

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`.

class Solution {
public:
bool canJump(vector<int>& nums) {
int size = nums.size();
if (size == 1)
return true;

std::vector<int> vec(nums.size(), 0);
vec[size — 1] = 1;
for (int i = nums.size() — 2; i > 0; i — ) {
int depth = nums[i];
while (depth != 0) {
if (i + depth >= size — 1 || vec[i + depth] == 1) {
vec[i] = 1;
break;
}
depth — ;
}
}
for (int i = 1; i <= nums[0]; i++) {
if (vec[i] == 1)
return true;
}
return false;
}
};

class Solution {
public:
bool canJump(vector<int>& nums) {
int size = nums.size();
if (size == 1)
return true;
int curPos = 0;
int dep = 0;
for (int i = curPos; i <= curPos + dep; i++) {
if (i + nums[i] > curPos + dep) {
curPos = i + nums[i];
dep = nums[curPos];
if (curPos + dep >= nums.size())
return true;
}
}
if (curPos + nums[curPos] >= size — 1) {
return true;
}
return false;
}
};

`public class Solution {    public boolean canJump(int[] nums) {        int lastPos = nums.length - 1;        for (int i = nums.length - 1; i >= 0; i--) {            if (i + nums[i] >= lastPos) {                lastPos = i;            }        }        return lastPos == 0;    }}`

BackTracking的複雜度是 O(2^n). 這個很難想，我下面就貼程式。

T(x) = T(x+1) + T(x+2) + …. + T(n);
T(x+1) = T(x+2) + …. + T(n);
T(x) = T(x+1) +[T(x+2) + …. + T(n)];
T(x) = T(x+1) + T(x+1);
T(x) = 2 * T(x+1);
.
.
.
T(x) = 2^(n-x-1)

T(1) 大約等於 2^n * T(n) = O(2^n)

`public class Solution {    public boolean canJumpFromPosition(int position, int[] nums) {        if (position == nums.length - 1) {            return true;        }        int furthestJump = Math.min(position + nums[position], nums.length - 1);        for (int nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) {            if (canJumpFromPosition(nextPosition, nums)) {                return true;            }        }        return false;    }    public boolean canJump(int[] nums) {        return canJumpFromPosition(0, nums);    }}`