# 55-Jump Game
###### tags: `Medium`
>question : https://leetcode.com/explore/interview/card/top-interview-questions-medium/111/dynamic-programming/807/

>reference :

>Key:
1. DP

>related problem :
## My Solution

class Solution {
    public boolean canJump(int[] nums) {
        boolean[] dp = new boolean[nums.length];
        dp[0] = true;
        for(int i = 0; i < nums.length; i++) {
            if(!dp[i])
                continue;
            for(int j = 1; j <= nums[i]; j++) {
                if(i + j < nums.length)
                    dp[i + j] = true;
            }
        }
        return dp[nums.length - 1];
    }
}

## Other Solution

class Solution {
    public boolean canJump(int[] nums) {
        int qualifiedIndex = nums.length - 1;
        
        for(int i = nums.length - 2; i >= 0; i--) {
            if(nums[i] >= (qualifiedIndex - i)) {
                qualifiedIndex = i;
            }
        }
        return qualifiedIndex == 0;
    }
}

## C++ Solution

class Solution {
public:
    bool canJump(vector<int>& nums) {
    int fin = nums.size();
    int dp = 0;
    for(int i=0 ; i < fin ; i++)
    {
        if(dp >= i)
        {
            dp = max(nums[i]+i, dp);
            if(dp >= fin-1)
            {
             return true;   
            }
        }
    }
    return false;
    }
};

>改成先判斷false，就能簡化成一個if(最優解)

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