문제

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

구현 전 예상 풀이

재귀로 적으로 다음 노드를 방문해서 마지막까지 가는지 풀어보겠다.

class Solution {
    int[] nums;
    int destination;

    public boolean canJump(int[] nums) {
        this.nums = nums;
        destination = nums.length - 1;
        return jump(0);
    }

    private boolean jump(int idx) {
        if (idx >= destination) {
            return true;
        }

        int length = nums[idx];
        if (length == 0) {
            return false;
        }

        return jump(idx + length);
    }
}

[2,5,0,0] 케이스에서 실패하였다.
점프값은 최대를 말한다.
0, 1 인덱스를 방문하면 마지막에 도착 할 수있다.

구현 코드

class Solution {
    int[] nums;
    int destination;
    boolean[] visit = new boolean[10000];

    public boolean canJump(int[] nums) {
        this.nums = nums;
        destination = nums.length - 1;
        return jump(destination, 0);
    }

    private boolean jump(int idx, int length) {
        if (visit[idx]) {
            return false;
        }

        visit[idx] = true;

        if (nums[idx] < length) {
            return false;
        }

        if (idx == 0) {
            return true;
        }

        for (int i = 1; i <= idx; i++) {
            if (jump(idx - i, i)) {
                return true;
            }
        }

        return false;
    }
}

다른 사람 풀이

public boolean canJump(int[] nums) {
    int reachable = 0;
    for (int i=0; i<nums.length; ++i) {
        if (i > reachable) return false;
        reachable = Math.max(reachable, i + nums[i]);
    }
    return true;
}

55. Jump Game
다른 사람 풀이 링크