Jump Game

目录

• 题目链接
• 注意点
• 解法
• 小结

题目链接

Jump Game - LeetCode

注意点

解法

解法一：贪心算法，只关注能到达最远距离，如果能到达的最远距离大于结尾说明能到达，否则不能。并且如果i超过了能到达的最大距离说明不能到达，因为i是每次加一都能超过最大距离，小于i的所有位置都会走到某个最远距离为0的位置。时间复杂度O(n)

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

解法二：网上看来的解法 —— 动态规划。但是我并不能理解这个状态转移方程dp[i] = max(dp[i - 1], nums[i - 1]) - 1

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

小结

• 希望有大神可以详说一下解法二的思路 TAT