# 55. Jump Game

## 1.問題 

* 給予一個非負整數的array, 每個值表示可達的最大長度, 判斷是否能達到最後一個index

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LN_WxMoR1H8sx7vWDcZ%2F-LN_Y7QXcDKl3RhTuorF%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-09-29%20%E4%B8%8B%E5%8D%889.37.20.png?alt=media\&token=20a5d308-f091-4b4a-833c-2a3d4b7f5246)

## 2.想法 <a href="#id-2-xiang-fa" id="id-2-xiang-fa"></a>

* 提問
* function header, parameter
* test input
* 說明想法
  * 動態規劃, 由於需要判斷到最後時的剩餘步數是否>=0
  * 因此dp內所要儲存的值為到此格所剩餘的步數, 由於一開始就在0了, 因此dp\[0] = 0, 之後的位置所剩下的步數為前一個所剩餘的步數 -1, 所以dp\[1] = max(dp\[0], num\[0]) - 1;
  * 如果有dp為負數則回傳false
  * 最後判斷dp\[last]是否為0
* 測試計算複雜度
  * O(N)

## **3.程式碼** <a href="#id-3-cheng-shi" id="id-3-cheng-shi"></a>

```
class Solution {
public:
    bool canJump(vector<int>& nums) {
        vector<int> remain(nums.size(), 0);
        remain[0] = 0;
        for (int i = 1; i < nums.size(); i++) {
            remain[i] = max(remain[i - 1], nums[i - 1]) - 1;
            if (remain[i] < 0) {
                return false;
            }
        }
        return true;
    }
};
```