#include<stdio.h>
#include<limits.h>
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("%d\n",ans);
return 0;
}
a) O(1)
b) O(n)
c) O(n2)
d) O(5)
What is the space complexity of the following dynamic programming implementation used to find the minimum number of jump
-
answerhappygod
- Site Admin
- Posts: 899604
- Joined: Mon Aug 02, 2021 8:13 am
What is the space complexity of the following dynamic programming implementation used to find the minimum number of jump
Join a community of subject matter experts. Register for FREE to view solutions, replies, and use search function. Request answer by replying!