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.

分析：

state: f[i] == true if f[i] can be reached.

function: f[i] == true if f[j] == true (j < i) && A[j] >= i - j;

initialization: f[0] = true

answer: f[n - 1] (n = A.size() )

值得留意的一点是，对于A[0] == 0 && A.size() > 1的情况应该进行一次判断，第一个点如果等于0，那后面的永远都跳不到，没必要耽误时间。

解法：

class Solution {
public:
    /**
     * @param A: A list of integers
     * @return: The boolean answer
     */
    bool canJump(vector<int> A) {
        // write you code here
        if (A.size() == 0) {
            return true;
        }

        if (A[0] == 0 && A.size() > 1 ) {
            return false;
        }

        int n = A.size();
        vector<bool> res(n, false);

        res[0] = true;
        for(int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (res[j] == true && A[j] >= i - j) {
                    res[i] = true;
                    break;
                }
            }
        }

        return res[n - 1];
    }
};