leetcode筆記：Jump Game II

一. 題目描述

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

二. 題目分析

該題的大意是，給定一個數組，每個元素代表從該位置可以往後跳的距離，問從第一個位置跳到最後一個位置至少需要跳多少次。

與 Jump Game 有所不同的是，Jump Game 詢問該數組能否跳到最後一格，這道題要求算出跳的次數。解決的思路依舊是貪心，只需設置一個數組用來記錄跳的路徑即可。

三. 示例代碼

class Solution {
public:
    int jump(int A[], int n) 
    {
        int result = 0; // 當前已跳躍的次數
        int last = 0;   // 上一跳可達到的最遠距離
        int curr = 0;   // 當前一跳可達到的最遠距離
        for (int i = 0; i < n; ++i) 
        {
            // 無法向前繼跳直接返回
            if(i > curr)
                return -1;
            // 需要進行下次跳躍，則更新last和當前已執行的跳數result
            if (i > last) 
            {
                last = curr;
                ++result;
            }
            // 更新當前可跳達的最遠處
            curr = max(curr, i+A[i]);
        }
        return result;
    }
};

四. 小結

類似的解題思路還有BFS，後期可以驗證驗證。