LC 45. Jump Game II

https://leetcode.com/problems/jump-game-ii/description/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n, INT_MAX);
        f[0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j <= min(n - 1, i + nums[i]); j++) {
                f[j] = min(f[j], f[i] + 1);
            }
        }
        return f[n - 1];
    }
};

Time Complexity: O(n)
Space: O(n)

算是經典的 DP 題目，普普通通

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int curJump = 0;
        int curRange = 0;
        int nxtJumpRange = 0;
        for (int i = 0; i < n; i++) {
            if (i > curRange) {
                curJump += 1;
                curRange = nxtJumpRange;
            }
            nxtJumpRange = max(nxtJumpRange, i + nums[i]);
        }
        return curJump;
    }
};

Time Complexity: O(n)
Space: O(1)

本題可以優化到使用 space O(1)