Leetcode - 45. Jump Game II

문제

각 인덱스에서 최대 점프거리를 나타낸 배열이 주어진다. 0인덱스에서 시작해서 마지막 인덱스에 도달할 수 있는 최소 점프횟수는?

Input: nums = [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.

해결 DP

f(0) = min(f(1) ~ f(1+num[0])) 와 같은 점화식으로 재귀+memoization으로 풀기.

class Solution {
    int last_idx;
    vector<int> mem;
    vector<int> nums;
    
    int min_jump(int cur) {
        if (cur == last_idx)
            return 0;
        
        int local_min = 20000;
        int until_idx = std::min(last_idx, cur + nums[cur]);
        for (int i = cur + 1; i <= until_idx; i++) {
            if (mem[i] == -1)   // call recursion
                local_min = std::min(local_min, min_jump(i) + 1);
            else                // get memoization
                local_min = std::min(local_min, mem[i] + 1);
        }
        mem[cur] = local_min;
        return local_min;
    }
public:
    int jump(vector<int>& orig) {
        last_idx = orig.size() - 1;
        mem = vector<int>(orig.size(), -1);
        nums = orig;
        return min_jump(0);
    }
};

해결 gready O(n)

솔루션 참고. 풀이 다시 살펴볼것.

#define max(a, b) (((a) > (b)) ? (a) : (b))
int jump(int* nums, int numsSize){
    int maxidx = 0;
    int curjumpend= 0;
    int cnt = 0;
    for (int i = 0; i < numsSize - 1; i++) {
        maxidx = max(maxidx, i + nums[i]);
        if (i == curjumpend) {
            cnt++;
            curjumpend = maxidx;
        }
    }
    return cnt;
}