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

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

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

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

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

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

C++

// greedy class Solution { public: bool canJump(vector& 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& nums) { vector 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]; } }

from http://tiggeul.tistory.com/9 by ccl(A) rewrite - 2021-10-15 23:01:52