leetcode Problem: 55. 跳躍游戲

思路

假設我們是一個小人，從第一個下標開始，每次經過一個位置，我們就可以根據當前位置的數值nums[i]和位置下標i計算出該位置所能到達的后續位置的最大值r=nums[i]+i。而這個r之前的區域一定都是可以經過的。那么我們就讓小人經過這一段區域，同時不斷更新r的值。r得到更新后繼續走繼續更新。直到走到終點或者說走到r對應的位置就停止（此時已無法繼續前進）。如果停在了r的位置，那么說已經無法繼續更新使得小人能繼續走下去了，這時若沒到達終點，就說明小人無法到達終點。

hint：其實這道題和 小人過橋 這個小游戲很類似（長按屏幕就能讓橋不斷變長）：0就是懸崖，>0則是地面。不同的點在于這里的橋的長度是由地面上的數字來決定。

代碼

class Solution {
public:bool canJump(vector<int>& nums) {int i=0,n=nums.size(),r=0;while(i<n&&i<=r)r=max(r,i+nums[i++]);return i>=n;}
};