(DP, Medium) Jump Game

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

DP는 익숙해지지가 않음..

핵심 아이디어는 i + nums[i] 가 goal보다 크거나 같으면 닿을 수 있다는 것

goal은 다시 i로 초기화하고 점진적으로 0까지 갈 수 있는지 확인하면 된다.

i + nums[i] >= goal 이라면 i까지만 와도 유효하기 때문

다시 goal = i로 초기화해서 반복하면 마지막 탐색 i가 첫 인덱스에서 접근 가능하다면 0일것이고 아니면 접근 불가이므로 false다.

시간복잡도 O(n)이다.

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