C++跳跃游戏（青蛙跳）

116. 跳跃游戏
中文English
给出一个非负整数数组，你最初定位在数组的第一个位置。　　　

数组中的每个元素代表你在那个位置可以跳跃的最大长度。　　　　

判断你是否能到达数组的最后一个位置。

样例
样例 1

输入 : [2,3,1,1,4]
输出 : true
样例 2

输入 : [3,2,1,0,4]
输出 : false
注意事项
这个问题有两个方法，一个是贪心和 动态规划。

贪心方法时间复杂度为O（N）。

动态规划方法的时间复杂度为为O（n^2）。

我们手动设置小型数据集，使大家可以通过测试的两种方式。
这仅仅是为了让大家学会如何使用动态规划的方式解决此问题。
如果您用动态规划的方式完成它，你可以尝试贪心法，以使其再次通过一次。

class Solution {
public:
    /**
     * @param A: A list of integers
     * @return: A boolean
     */
    bool canJump(vector<int> &A) {
        // write your code here
        int n = A.size();
        bool *f = new bool[n];
        f[0] = true; //因为最初在第一个位置，那么肯定就是能跳到。
        
        for(int i = 1; i < n; i++){
            //我们就假设当前的下一个位置是跳不到的
            f[i] = false;
            //枚举要跳到的位置之前的一个情况
            for(int j = 0; j < i; j++){
                //如果出现前一个位置能跳到并且
                //前一个位置加上ta的最长跳跃度是大于i的（i是要跳到的那个位置）
                //那么i这个位置就是可以跳到的
                if(f[j] && j + A[j] >= i){
                    f[i] = true;
                    break;
                    //break的原因是，因为我们只要求能够跳到当前i的位置
                    //所以只要出现一种能跳到的情况就可以了
                }
            }
        }
        return f[n - 1];
    }
};