算法設計與應用基礎：第九周（1）

55. Jump Game

Add to List Description Hints Submissions Solutions

• Total Accepted: 116148
• Total Submissions: 396095
• Difficulty: Medium
• Contributor: LeetCode

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position. 

Determine if you are able to reach the last index.

For example:

A = 

[2,3,1,1,4]

, return 

true

.

A = 

[3,2,1,0,4]

, return 

false

.

解題思路：看到這道題最容易想到的思路就是暴力求解：周遊數組内所有點，若它之前被标記過（到達過），就标記它可達範圍内的所有點，最後檢查最後一個點是否被标記。

直接的想法，但是不幸的是它的複雜度會達到n^2，在大資料面前就不可行了，是以需要采取更高效的方法進行“周遊”（這次要去掉一些沒必要的步驟，也就是優化），這和最一開始講的貪婪算法的基礎内題很像，是以采取這個思路，每次記錄在該點能到達的最大點（假裝直接跳到這個點，這就是貪婪的關鍵，後面會證明這個算法的準确性），然後周遊在這個最大點和目前點之間的所有點，檢查它們的nums[i]+i和最大點的關系，大于就修改。當周遊到i>furthest 的時候就結束（表明這時的furthest是能達到的最遠點了）。

算法的正确性：每走一步都是走到的最遠點（局部最優可以退出全局最優，因為是一步一步來的），這樣就利用貪婪的算法過濾了沒必要的周遊，大大減少了時間複雜度到n。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int size=nums.size();
        int furthest=0;//the furthest you can jump to till now;
        for(int i=0;i<size;i++)
        {
            if(i>furthest)
                break;
            else
                furthest=max(nums[i]+i,furthest);
        }
        return furthest>=size-1;
        
    }
};
           

 後記：greed algorithm的關鍵是證明局部最優是全局最優（因為往往局部最優容易去到）；或者利用局部最優來接近全局最優。