[leetcode][C++][Java] jump game

https://leetcode.com/problems/jump-game/

Jump Game - LeetCode

 

[leetcode][C++][Java] jump game

처음 보자마자 생각난건 dp..

greedy로 풀면 코드도 간결하고 java로도 1ms가 나온다.

 

 

 

C++

// greedy
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int last = nums.size() - 1;

        for (int i = nums.size() - 1; i >= 0; i--) {
            if (i + nums[i] >= last)
                last = i;
        }

        return last == 0;
    }
};

//dp
class Solution {
public:
    bool canJump(vector<int>& nums) {
        vector<bool> dp(nums.size(), false);
        dp[0] = true;

        for (int i = 0; i < nums.size(); i++) {
            if (!dp[i]) continue;
            int mx = min(i + nums[i], int(nums.size() - 1));
            for (int j = i + 1; j <= mx; j++) {
                dp[j] = true;
            }
        }

        return dp[nums.size() - 1];
    }
};

 

 

Java

// greedy
class Solution {
    public boolean canJump(int[] nums) {
        int len = nums.length;
        int last = len - 1;

        for (int i = len - 1; i >= 0; i--) {
            if (i + nums[i] >= last)
                last = i;
        }
        return last == 0;
    }
}

// dp
class Solution {
    public boolean canJump(int[] nums) {
        int len = nums.length;
        boolean[] dp = new boolean[len];
        dp[0] = true;

        for (int i = 0; i < len; i++) {
            if (!dp[i]) continue;
            for (int j = 1; j <= nums[i]; j++) {
                if(i + j >= len) break;
                dp[i + j] = true;
            }
        }

        return dp[len - 1];
    }
}