30 Day Challenge Day 11 | Leetcode 55. Jump Game

题解

入门级的动态规划题。

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

可以进一步优化，用一个变量代替数组。

runtime可以从1488ms优化到20ms。

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