題面：

LeetCode 45 跳躍游戲2

數據范圍：

$1\le nums.length\le 10^4$
$0\le nums[i]\le 1000$
題目保證可以到達 $nums[n?1]$

思路 & code：

1. dp暴力思路

往前找，如果前面某個點能到當前點 $index$，及存在 $k<i$ 使得 $k+nums[k]\ge i$，則更新 dp(dp[i]存儲到當前 $i$ 點所需最小步長)，$dp[i]=min(dp[i],dp[k]+1)$

時間復雜度： $O(n)$
空間復雜度： $O(n)$

size_t n = nums.size();
vector<int> dp(n, 0x3f3f3f3f);
dp[0] = 0;
for(int i = 1; i < n; ++i)for(int k = 0; k <= i; ++k)if(k + nums[k] >= i)dp[i] = min(dp[i], dp[k] + 1);

2. dp + 貪心 + 雙指針：即第一個跳到當前點 $i$ 的點 $j$，必是步數最少的。

**證明：**假設有一個點 $p>j$, 其跳到點 $i$ 的步數小于點 $j$ 跳到點 $i$ 的步數。則有 $dp[p]+1<dp[j]+1$, 即 $dp[p]<dp[j]$。由于 $dp[k]$ 存儲的是跳到 $k$ 點的最短步長，又 $j<p$, 故能跳到 $p$ 點的一定也能跳到 $j$ 點，即$dp[j]\le dp[p]$ 的，故原式不成立。所以第一個跳到當前點i的點j必是步長最小的。

時間復雜度： $O(n)$
空間復雜度： $O(n)$

size_t n = nums.size(), j = 0;
vector<int> dp(n, 0);
for(size_t i = 1; i < n; ++i) {while(j + nums[j] < i) ++j;dp[i] = dp[j] + 1;
}
return dp[n-1];

3. 貪心+滑動窗口

維護一個當前能到達的最大邊界（窗口），每次更新邊界時，步數++。通俗理解就是因為當前的最大邊界就是這一步能跳到的，如果想跳出更大的，則需要繼續跳一步才行。

時間復雜度： $O(n)$
空間復雜度： $O(1)$

int jump(vector<int>& nums) {/* 維護兩個端點，left & rightsize_t n = nums.size(), left = 0, right = 0;size_t maxPos = 0, step = 0;while(right < n - 1) {for(auto i = left; i <= right; ++i)maxPos = max(maxPos, i + nums[i]);left = right + 1;right = maxPos;++ step;}return step;*//* 優化, left其實沒有貢獻, 一遍遍歷只維護right即可*/size_t n = nums.size(), step = 0;size_t right = 0, maxPos = 0;for(size_t i = 0; i < n - 1; ++i) {maxPos = max(maxPos, i + nums[i]);if(i == right) {right = maxPos;++ step;}}return step;
}