[OJ.leetcode] jump-game-ii

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

Given an array of non-negative integers, you are initially positioned at the first index of the array. 

Each element in the array represents your maximum jump length at that position. 

Your goal is to reach the last index in the minimum number of jumps. 

 For example: Given array A = [2,3,1,1,4] 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.)

/* 전수조사 해야하는가? yes O(n^2) solution: 각 ele에 도달하는 mininum jump 수를 계산 class Solution { public: int jump(int A[], int n) { int* B = new int[n]; int minJump = INT_MIN; memset(B, 0, sizeof(B)); B[0] = 0; for(int i=0; i<n; i++) { for(int j=i ; j>=0 ; j--) { if(A[j] >= i) { B[i] = min(B[i], B[j]+1); if(n-j <= A[i]) return B[i]; } } } return B[n-1]; } }; 전수조사 해야하는가? no O(n) solution : greedy algorithm 으로, 현재 점프 범위내에서 가장 멀리갈수있는 maximum jump 값을 찾아나가면 된다. 아이디어 자체는 금방 떠올렷으나, O(n)으로 구현해내는 것이 생각보다 잘 안되어서 애 먹음. (특히 loop하나로 현재 점프 범위를 유지하면서) 다음 점프 범위를 max 함수로 찾아내는 부분 구현이 잘 안됨. */ class Solution { public: int jump(int A[], int n) { if(n <= 1) return 0; int prevJumps = 0; int jumps = 0; int maxDistance = 0; for(int i=0; i<n ; i++) { if(i > prevJumps) { prevJumps = maxDistance; jumps++; } maxDistance = max(maxDistance, A[i]+i); if(maxDistance >= n-1) return (jumps+1); //greedy algorithm 이므로, 현재 상태가 '최선'의 선택임. } return jumps; } };