# 45 - Jump Game II

解法一 - 不斷從頭尋找能跳到 end 的最前面 index

最直觀的 greedy 解法就是看最早能跳到 end 的 index 是哪一個，然後把這個 index 當成新的 end，直到回到出發位置。實作如下：

class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size()<2) return 0;

        int jump=0, start=0, end=nums.size()-1;

        while(start < end) {
            for(int i=start; i<end; i++) {
                if(i+nums[i] >= end) {
                    jump++;
                    end = i;
                    break;
                }
            }
        }

        return jump;
    }
};

這解法很直觀，可惜會 TLE：

解法二 - BFS

我們可以把這題想成一個 BFS 的題目，把 i-th jump 可以到達的 index 放在第 i 層。可以參考 [這個 Leetcode 討論串](https://leetcode.com/problems/jump-game-ii/discuss/18019/10-lines-C%2B%2B-(16ms)-Python-BFS-Solutions-with-Explanations)。\

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size(), step = 0, start = 0, end = 0;

        while (end < n - 1) {
            step++; 
            int maxend = end + 1;
            for (int i = start; i <= end; i++) {
                if (i + nums[i] >= n - 1) return step;
                maxend = max(maxend, i + nums[i]);
            }
            start = end + 1;
            end = maxend;
        }

        return step;
    }
};

還有另一個寫起來更簡潔的做法：

class Solution {
public:
    int jump(vector<int>& nums) {
        int jumps = 0, curEnd = 0, curFarthest = 0;

        for (int i = 0; i < nums.size() - 1; i++) {
            curFarthest = max(curFarthest, i + nums[i]);
            if (i == curEnd) {
                jumps++;
                curEnd = curFarthest;
            }
        }

        return jumps;
    }
};

解法三 - DP

首先定義一下 subproblem：

dp[i] = 到 index i 所需要的最少 jump 數

所以我們就知道 dp[i] = min(dp[前面所有可以到達 i 的 index]+1)。或是我們可以反過來說，我們看目前這個 index 可以到的範圍(start ~ end)，然後就看 dp[end] 比較小（從其他地方跳到 end 所需 jump 數），還是 dp[start]+1 比較小（表示從 start 跳一步到達 end）。

class Solution {
public:
    int jump(vector<int>& nums) {
        vector<int> dp(nums.size());

        // Init with infinity, except the first index which should be 0 
        for (int i = 1; i < nums.size(); i++) {
            dp[i] = numeric_limits<int>::max();
        }

        for (int start = 0; start < nums.size()-1; start++) {
            for (int end = start+1; end <= start+nums[start] && end<nums.size(); end++) {
                dp[end] = min(dp[end], dp[start] + 1);
            }
        }

        return dp[nums.size() - 1];
    }
};

這個解法是正確的，可惜會 TLE。