這題簡單來說就是一個陣列，其中的數字代表最多能跳幾格 問是否能走到最後一個點(其中的數字為非負整數) 解題思路： 首先如果你對於 DP 有點了解，應該能輕易地看出這是 DP 那就直接照著題目的敘述邏輯去實作，應該會像下面這樣 ```cpp= vector<bool> dp(n, false) ; dp[0] = true ; for (int i=0;i<n;i++) { if (dp[i] == false) break ; for (int j=i+1;j<n && j<=i+A[i];j++) dp[j] = true ; } return dp[n-1] ; ``` ```python= dp = [False for x in range(n)] dp[0] = True for i in range(0, n) : if (not dp[i]) : break for j in range(i+1, min(i+A[i]+1, n)) : dp[j] = True return dp[n-1] ``` 但是這樣時間複雜度是多少，很明顯來到 $O(n^2)$ 對於這題來說，這樣的時間複雜度大概率是會爆的，所以我們要去優化 先觀察不同的狀態，在操作當中常常會走已經走過的路，比如下面的圖 ![image alt](https://i.imgur.com/4ecYALR.png =70%x) 圖上綠色的箭頭指向前一個位置，橘色的箭頭代表現在的位置 深綠的箭頭代表前一個操作走的路，深紅的箭頭代表優化前走的路 最後紫色的箭頭是優化後走的路，實作只要多一個變數 X 紀錄深綠箭頭走到哪即可 至於第二個特性，如果根據之前的做法，到綠深綠箭頭結尾前的每一個點 都是可以走的，也就是說，或許我們也不用走完全的深綠箭頭，只需要紀錄終點就好 1. 走過的路不用再走，並且記錄之前走過最遠的點 2. 只需要記錄路徑的最尾端，其前方的點當作有走過 根據這兩個特性，不難發現其實我們根本不需要紀錄那些點有走過 或許只需要紀錄目前最尾端走到哪個點 Y，Y 點前的所有點都可以當作已經走過 換句話說，所有路徑都可以壓縮成一個結尾，只要判斷最後結尾有沒有到終點就行 所以我們可以把程式碼修改成這樣 ```cpp= int ans = A[0] ; for (int i=1;i<n;i++) { if (ans < i) return false ; // 代表無法走到 i 失敗了 ans = max(ans, i+A[i]) ; } return true ; // 能走到 n-1 代表一定過 ``` ```python= ans = A[0] for i in range(1, n) : if (ans < i) : return False ; ans = max(ans, i+A[i]) ; return true ; ``` 這樣時間複雜度會變成 $O(n)$，空間複雜度也是常數而已 透過壓縮狀態的表示，能夠讓 DP 有更進一步的優化 當然也可以說這是一種狀態轉換，畢竟是從"看哪些點走過"變成"哪個走過的點最遠"