這題是 [Jump Game](https://hackmd.io/@apcser/SJCOx2kAA) 的延伸，題目敘述基本上是差不多，可以目的變成走幾步能到終點(肯定能走) 解題思路 : 同樣的概念，這題最直觀的方法就是透過某個點 X 往後走，判斷走到的點 Y，Y 的目前步數與 X+1 哪個比較大 同樣使用 DP 會像是下面的程式碼所展現的一樣 ```cpp= vector<int> dp(n, 1e9) ; dp[0] = 0 ; for (int i=0;i<n;i++) for (int j=i+1;j<n && j<=i+A[i];j++) dp[j] = min(dp[j], dp[i]+1) ; return dp[n-1] ; ``` 這樣的時間複雜度為 $O(n^2)$，在這題可以通過，因為最大差不多是 $10^7$ 如果轉換一下思路呢，這裡都是在某點到下一個點的步數比較，所以一個點可能會被走好幾次 換句話說，我們如果找到只需要一次走過每個點的方式就能大幅度減少計算的時間，如下圖 ![image alt](https://i.imgur.com/NWVK3T9.png) 比較下面的藍色箭頭其實根本不需要做，因為前者用"同樣步數"走到更後面了 所以這裡可以得出一個結論，在同樣步數的情況下，我們只需要保留最末端 最末端之前(包含)到前一步的最末端之後(不包含)步數都相同，在圖片的例子內 第三個 1 之前(包含)與第二個 1 之後(包含)都是兩步，而 3 所在的位置是第一步的最尾端(包含) 所以更進一步的說，我只要記錄不同步數的最尾端在哪裡就好 這樣跟上面的做法完全相反，上方用點當作 index，這裡用步數當作 index 這樣只要根據步數的增加配合 for 迴圈就能找出每個步數對應的最末點 也就能找出答案 ```cpp= int lvl = 0, n = A.size() ; vector<int> step(n, 0) ; // 第 lvl 次跳躍最遠能到哪裡 for (int i=0;i<n-1;i++) { step[lvl+1] = max(step[lvl+1], i + A[i]) ; // 更新該步數最遠的點 if (i == step[lvl]) lvl++ ; // 已經走到第 lvl 次跳躍的最遠距離了 } return lvl ; // 幾步走到終點 ``` 這樣時間複雜度就能降到 $O(n)$，額外的空間其實可以用新增的 但速度方面可能會變慢，看個人如何去取捨，我是喜歡一次到位的