leetcode筆記：Jump Game

一. 題目描述

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.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.

二. 題目分析

該題的大意是，給定一個數組，從第一個元素開始，元素的值表示能夠往後跳的最大距離，問按照這種規則，該數組是否能跳到最後一個元素。

解題的基本思路是貪心算法。當然，使用動態規劃也是完全可以解決的，也貼出網上一種動規代碼。

三. 示例代碼

// greedy algorithm
class Solution {
public:
    bool canJump(int A[], int n) {
        if(n == 0 || n == 1){
            return true;
        }
        int maxStep = A[0];
        for(int index = 1 ; index < n ; ++index)
        {
            if(maxStep == 0) return false;
            --maxStep; 
            if(maxStep < A[index])
                maxStep = A[index];
            if(maxStep + index >= n - 1) // 滿足條件
                return true;
        }
    }
};

// DP algorithm
class Solution {
public:
    bool canJump(int A[], int n) 
    {
        vector f(n, 0);
        f[0] = 0;
        for (int i = 1; i < n; i++) 
        {
            f[i] = max(f[i - 1], A[i - 1]) - 1;
            if (f[i] < 0) return false;
        }
        return f[n - 1] >= 0;
    }
};

四. 小結

該題的思路是，使maxStep一直保持最大的能移動步數。