Leetcode - 55. Jump Game

문제

다음 인덱스로 점프할수 있는 최대 거리가 기록된 배열이 주어진다. [0] 부터 점프를 시작한다고 할때, 마지막 인덱스에 도달할 수 있는지 없는지 판단하라.

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

아이디어

• O(n^2)
  맨마지막-1 부터 [0] 까지 앞으로 하나씩 파악한다. 그리고 현재 인덱스에서 갈수 있는 최대 거리까지 모두 탐색한다. 그리고 mem[] 배열에 따로 저장하고 true가 있는지 체크. 최악의경우 O(n^2)의 시간복잡도를 갖고 O(n)의 공간복잡도를 갖는다.

2 4 2 1 0 4 0 0 0 3
T T F F F T F F F

• O(n) DP + memoiazation
  f(i) = f(i+1) ~ f(i+num[i]) 중에 true가 있으면 true리턴. (back tracking 기반)
  재귀적으로 반복하고 이미 풀었던 계산은 메모이제이션하기.

해결 O(n^2)

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int nsize = nums.size();
        if (nsize == 1) return true;
        vector<bool> mem(nsize, false);
        for (int i = nsize - 2; i >= 0; i--) {
            for (int j = i; j <= i + nums[i]; j++) {
                if (j == nsize - 1 || mem[j] == true) {
                    mem[i] = true;
                    if (i == 0)
                        return true;
                    break;
                }
            }
        }    
        return false;
    }
};

해결 DP O(n)

드라마틱하게 빨라지지는 않았음.

class Solution {
    vector<int> mem;
    int last_idx;
    bool check_reach(vector<int>& nums, int cur, int end) {
        if (mem[cur] != -1)
            return mem[cur];
        if (cur == last_idx)
            return true;
        if (end > last_idx)
            end = last_idx;
        for (int i = cur + 1; i <= end; i++) {
            if (mem[i] == -1)
                mem[i] = check_reach(nums, i, i + nums[i]);
            if (mem[i] == true)
                return true;
        }
        mem[cur] = false;
        return mem[cur];
    }
public:
    bool canJump(vector<int>& nums) {
        last_idx = nums.size() - 1;
        if (last_idx == 0) return true;
        mem = vector<int>(nums.size(), -1);
        
        return check_reach(nums, 0, nums[0]);
    }
};