一. 簡介

前面一篇文章使用貪心算法解決 力扣網55題：跳躍游戲，文章如下：

力扣網編程55題：跳躍游戲之貪心算法-CSDN博客

二.?力扣網編程55題：跳躍游戲之逆向思維

給你一個非負整數數組 nums ，你最初位于數組的 第一個下標 。數組中的每個元素代表你在該位置可以跳躍的最大長度。
判斷你是否能夠到達最后一個下標，如果可以，返回 true ；否則，返回 false 。

示例 1：
輸入：nums = [2,3,1,1,4]
輸出：true
解釋：可以先跳 1 步，從下標 0 到達下標 1, 然后再從下標 1 跳 3 步到達最后一個下標。

示例 2：
輸入：nums = [3,2,1,0,4]
輸出：false
解釋：無論怎樣，總會到達下標為 3 的位置。但該下標的最大跳躍長度是 0 ， 所以永遠不可能到達最后一個下標。

逆向思維分析：

采用逆向思維，從終點倒推判斷哪些位置可以到達終點。

從最后一個位置開始往前遍歷，維護一個變量 last_pos：表示當前能夠跳到到終點的最近位置。

如果 index+ nums[index] >= last_pos，就更新 last_pos為當前位置 index（因為index是新的可到達終點的最小下標）。

遍歷完數組，最后判斷 last_pos是否為0；

解題思路二：（從后往前逆向思維）

1. 定義一個變量last_pos：初始化為numsSize-1，表示當前能夠跳到終點的最近位置。

2. 遍歷數組，從倒數第二個元素開始，判斷當前位置+跳躍的長度（即數組元素值）是否大于等于 last_pos，如果滿足，則將last_pos = i（因為 index是新的可到達終點的最小下標）；

3. 數組遍歷結束，最后判斷last_pos是否為0，如果是則說明數組從首元素可以跳躍到終點，否則不行；

C語言實現如下：

//逆向思維
//從數組末尾開始，從后往前遍歷
bool canJump(int* nums, int numsSize) {//last_pos表示能到達終點位置的最近位置//初始時，終點位置是可到達的int index;int last_pos = numsSize-1;for(index = numsSize-1; index >= 0, index--) {//關鍵判斷：//如果從當前位置index出發，跳躍nums[index]長度的距離能夠到達或超過last_pos//說明可以從index位置跳躍到last_pos的位置，進而到達終點//因為更新last_pos為index，因為現在index成為了新的可到達終點的最前位置if((index + nums[index] >= last_pos)) {last_pos = index;}}if(!index){return true;}else{return false;}
}