LeetCode 55 Jump Game

    
        标签：
        
            LeetCode
        
    发布于：2021-06-01 15:50:12
    编辑于：2021-06-01 16:02:49
    浏览量：1022

https://leetcode.com/problems/jump-game/

分析

显然可以直接暴力遍历 + cache 求解。

动态规划递归解法

1028 ms 53 MB，性能挺差的，毕竟时间复杂度：O(nm)。

状态的定义是从位置 i 能否到达最后一个索引。

class Solution {
public:
    vector<short> dp;
    vector<int> nums;
    
    bool canJump(vector<int>& nums) {
        this->nums = nums;
        vector<short> dp(nums.size(), -1);
        this->dp = dp;
        return helper(0);
    }
    
    bool helper(int p) {
        if (dp[p] != -1) return dp[p] == 1;
        bool ok = false;
        if (nums[p]+p>=nums.size()-1) {
            ok = true;
        } else {
            for(int i=1;i<=nums[p];i++) {
                if (helper(p+i)) {
                    ok = true;
                    break;
                }
            }
        }
        dp[p] = ok ? 1 : 0;
        return ok;
    }
};

高赞 O(n) 迭代解法

https://leetcode.com/problems/jump-game/discuss/20917/Linear-and-simple-solution-in-C%2B%2B

思路是求从起始位置能到达的最远处，每次迭代更新可以到达的最远距离。

bool canJump(int A[], int n) {
    int i = 0;
    for (int reach = 0; i < n && i <= reach; ++i)
        reach = max(i + A[i], reach);
    return i == n;
}

真的 6 啊。

另一个高赞 O(n) 迭代解法

https://leetcode.com/problems/jump-game/discuss/20900/Simplest-O(N)-solution-with-constant-space

思路是求从最后的索引出发能反向到达的最远处，每次迭代更新可以到达的最远距离。

bool canJump(int A[], int n) {
    int i = 0;
    for (int reach = 0; i < n && i <= reach; ++i)
        reach = max(i + A[i], reach);
    return i == n;
}

Links: leetcode-55-jump-game