---
# System prepended metadata

title: Leetcode 45. Jump Game II
tags: [Leetcode(C++)]

---

# Leetcode 45. Jump Game II
###### tags: `Leetcode(C++)`

題目 : https://leetcode.com/problems/jump-game-ii/ 。

想法 : 類似上一題，因題目保證可以走到底，直接紀錄陣列狀態 : 走到這部為止最小步數。

時間複雜度 : O(nm)。

程式碼 :

```
class Solution {
public:
    int jump(vector<int>& nums) {
        int l=nums.size(),step[20010];
        for(int i=0 ; i<l ; i++) step[i]=10010;
        step[0]=0; step[1]=1;
        
        for(int i=0 ; i<l ; i++){
            for(int j=i+1 ; j<=i+nums[i] ; j++){
                step[j]=min(step[j],step[i]+1); 
            }
        }
        
        return step[l-1];
    }
};
```