題目網址：https://leetcode.cn/problems/jump-game/

題意：給一非負整數 array nums, 最初位置在 nums[0], 其中 nums 中的每個元素代表該位置可以跳躍的最大長度, 返回是否能從起點抵達最後一個 index。

Solution 1：

想法：利用 DP, 其中 dp[i] 代表第 i 個點能否被抵達, 條件是 i 前面的任意點 j 能被抵達 （dp[j] = true）, 且能從 j 跳到 i （j + nums[j] >= i ）, 故得到狀態轉移方程：

  • dp[i] = (dp[j] == true) && (j + nums[j] >= i), 其中 0 ≤ j < i

從下圖中可看到, 從 idx = 2 開始往後走的有重複, 故用 cache 把結果存起來, 避免重複計算

class Solution {
public:
    bool canJump(vector<int>& nums) {
        const int n = nums.size();
        vector<bool> dp(n, false);
        dp[0] = true; // 起點一定能抵達

        for (int i = 1; i < n; ++i) {
            for (int j = i - 1; j >= 0; --j) {
                // 第 j 個點能被抵達 && 能從 j 跳到 i
                if (dp[j] && j + nums[j] >= i) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp.back();
    }
};
  • time：$O(n^2)$ ➔ for loop
  • space：$O(n)$ ➔ dp

Solution 2：

想法：利用 Greedy, 從終點往回推, 只要有某點能到達終點, 就把該點設為終點（因為其他點只要能到達該點, 就一定能抵達終點）。若最後終點等於 0, 則代表能從起點能走到終點

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int goal = nums.size() - 1;

        for (int i = goal - 1; i >= 0; --i) {
            if (i + nums[i] >= goal) {
                goal = i;
            }
        }

        return goal == 0;
    }
};
  • time：$O(n)$ ➔ for loop
  • space：$O(1)$ ➔ 只需常數空間