55. Jump Game

greedy O(n) time - best!
计算每个位置所能到达的最远的位置（选择最远的，即贪心），并维护一个全局当前可以到达的最远位置，如果当前的位置比当前的全局可以到达的最远位置还要远，证明当前位置无法达到，那么最后一个位置也不可能从第一个位置到达

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        for (int i = 0, curr_max = 0; i < n && curr_max < n - 1; ++i) {
            if (i > curr_max) return false;
            curr_max = max(curr_max, i + nums[i]);
        }
        return true;
    }
};

dp O(n²) time O(n) space TLE
问题：n是否可以跳到
最后一步：从i跳到n-1，需要满足i + A[i] >= n - 1并且i可以跳到
子问题：i是否可以跳到
状态转移方程：f[i] = f[j] && j + A[j] >= i where 0 <= j < i
初始条件：f[0] = true

class Solution {
public:
    bool canJump(vector<int>& nums) {
        if (nums.empty()) return false;
        int n = nums.size();
        vector<bool> f(n);
        f[0] = true;
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (f[j] && j + nums[j] >= i) {
                    f[i] = true;
                    break;
                }
            }
        }
        return f[n - 1];
    }
};