2021-11-02 leetcode 动态规划 55.跳跃游戏 c++

2021-11-02 leetcode 动态规划 55.跳跃游戏 c++

leetcode 55.跳跃游戏

要素
已知nums[n]
nums[I]为可跳跃的最大长度，即可跳跃距离<=nums[i]
从nums[0]开始，通过不断跳跃是否能达到nums[n-1]
思路
1:nums[0]跳跃后的范围内所有格子都可以作为起跳点，eg:nums[0] = 3,则后面3个格子都可以作为起跳点。
2:每个格子作为起跳点能够达到的最大距离记作maxStep，每个起跳点都跳到最远距离来更新maxStep
3:若maxStep >= n-1，即能一直跳到最后，则成功

class Solution {
public:
    bool canJump(vector& nums) {
        int maxStep = 0;//最远距离
        for(int i = 0; i < nums.size(); i++) {
            if(maxStep < i) //最远距离<某个格子的距离，即不能跳到最后，甚至不能到某一个格子
                return false;
            maxStep = max(maxStep, i + nums[i]);//最远距离maxStep的更新
        }
        return true;//能跳到最后
    }
};