LeetCode - 55. Jump Game

Category: Algorithm
Difficulty: Medium
Tags: Array, Greedy
Discription: https://leetcode.com/problems/jump-game/#/description

這題感覺像是跳格子，依你所在陣列位置上的值決定可以跳的步數。
舉例：

A = [2, 3, 1, 1, 4] return true  -----> 可以順利由A[0]走到最後A[4]
B = [3, 2, 1, 0, 4] return false -----> 走到A[3]卡住，走不到A[4]

在這裡實作上沒有別的重點，就是貪婪法！
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int i, lastpos = nums.size()-1;
        for(i=lastpos; i>=0; i--)
            if(i+nums[i]>=lastpos){
                lastpos = i;
            }
        return lastpos==0;
    }
};

這裡比較重要的演算法就是動態規劃(Dynamic Programming)，
以DP的方式記錄最後到達點(lastpos)，如此使得時間複雜度只有O(n)。

由於以由前往後走訪實踐DP的話，會需要多宣告一個「現在到達最遠位置」的記憶體空間，
因此，為了節省記憶體，我選擇讓陣列由後往前走訪，
如此一來，只要比對相鄰元素是否可以到達並記錄下來(lastpos)即可。