MCQ Practice
What is the space complexity of the following dynamic programming implementation used to find the minimum number of jumps? #include #include int min_jump(int *arr, int len) { int j, idx, jumps[len]; jumps[len - 1] = 0; for(idx = len - 2; idx >= 0; idx--) { int tmp_min = INT_MAX; for(j = 1; j <= arr[idx] && idx + j < len; j++) { if(jumps[idx + j] + 1 < tmp_min) tmp_min = jumps[idx + j] + 1; } jumps[idx] = tmp_min; } return jumps[0]; } int main() { int arr[] ={1, 1, 1, 1, 1, 1, 1, 1, 1},len = 9; int ans = min_jump(arr,len); printf("%dn",ans); return 0; }
Subject: ComputerTopic: Dynamic Programming In Data Structures
Correct Answer: B
