> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/leetcode/55.-jump-game.md).
# 55. Jump Game
## 1.問題
* 給予一個非負整數的array, 每個值表示可達的最大長度, 判斷是否能達到最後一個index
## 2.想法
* 提問
* 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.程式碼**
```
class Solution {
public:
bool canJump(vector& nums) {
vector 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;
}
};
```