貪心——55. 跳躍遊戲 && 45.跳躍遊戲II

給定一個非負整數數組，你最初位于數組的第一個位置。

數組中的每個元素代表你在該位置可以跳躍的最大長度。

判斷你是否能夠到達最後一個位置。

示例 1:

輸入: [2,3,1,1,4]

輸出: true

解釋: 我們可以先跳 1 步，從位置 0 到達 位置 1, 然後再從位置 1 跳 3 步到達最後一個位置。

示例 2:

輸入: [3,2,1,0,4]

輸出: false

解釋: 無論怎樣，你總會到達索引為 3 的位置。但該位置的最大跳躍長度是 0 ， 是以你永遠不可能到達最後一個位置。

這是55，我剛拿到的時候，是完全想不到貪心的，因為如果每一步都走最長的步數，是不一定能到達n-1的，這樣會錯過必經之路。

在之後，我就想到的回溯，如果從下标0開始周遊，不好控制回溯的思路，也不好構造回溯的記錄，是以我選擇：

用visited記錄：

0： 沒到過

-1：到不了

1： 到得了

從後往前回溯，目前位置為currIndex，如果currIndex前的點i沒通路到，且能到currIndex，visited[i]為1，否則為0

能到：i + nums[i] >= currIndex

currIndex前的點i沒通路到：visited[i] == 0

代碼如下：

看了題解，貪心的思路用一句話就可以總結：

每次走遍目前cover到的所有點，根據i + nums[i]的值更新cover，直到：

到達n-1

沒有新的點加入，即cover不能更新

到跳躍2，條件變成：

肯定能到n-1

跳躍次數min

是以貪心的思路變成：

每次在cover中，尋找能讓cover增加最多的點i，走到那兒

count++