跳跃游戏 —— 能否到达终点 https://leetcode.cn/problems/jump-game/description/

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

/* 判断【起点】能否（bool）到达【终点】     
        dp[0]                   dp[n-1]
总长度n  非负整数数组num[3]————>最多可往后跳0/1/2/3步
(法一) 【动态规划】
        i从起点右侧（dp[1]）遍历至终点（dp[n-1]）
            对于i左侧所有的j，满足——  j可达    &&   j往后能到达i   ==> dp[i]=true
                                    dp[j]=true       num[j]+j>=i

(法二) 【背包】step
        i从起点（dp[0]）遍历至终点（dp[n-1]）
            step从1累加至num[i]————> dp[i+step]=true
*/
#include<bits/stdc++.h>
using namespace std;

int main(){
    int n; // 数组长度
    cin>>n;
    vector<int> nums(n);
    vector<bool> dp(n);

    for(int i=0;i<n;i++){
        cin>>nums[i];
    }

    dp[0]=true;

    // 法一【j ——> i】
    for(int i=1;i<n;i++){
        for(int j=0;j<i;j++){
            if(dp[j] && j+nums[j]>=i){
                dp[i]=true;
            }
        }
    }
    cout<<boolalpha<<dp[n-1]<<endl;

    // 法二 【i———每一个step————>】
    for(int i=0;i<n;i++){
        for(int step=1;step<=nums[i];step++){
            dp[i+step]=true;
        }
    }
    cout<<boolalpha<<dp[n-1]<<endl;

    return 0;
}
/* 输入
5
2 3 1 1 4
*/