# 45 - Jump Game II

解法一 - 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。不過這邊的重點是想要 identify Fibonacci Number 的 pattern，所以還是列出這個解法。

解法二 - Greedy

Leetcode Wang 的解法寫得很清楚，直接借用：

int end = 0;
    int maxPosition = 0; 
    int steps = 0;
    for(int i = 0; i < nums.length - 1; i++){
        //找能跳的最遠的
        maxPosition = Math.max(maxPosition, nums[i] + i); 
        if(i == end){ //遇到邊界，就更新邊界，并且步数加一
            end = maxPosition;
            steps++;
        }
    }
    return steps;