Minimum number of jumps-dynamic programming
in an array where each element represents the max number of steps it can take from that element. we should find the minimum number of jumps to reach the end of the array (starting from the first element). If an element is 0, then cannot move through it
lets take an example:
n= 11
a[11]= 1 3 5 8 9 2 6 7 6 8 9
First jump from 1st element, and we jump to 2nd element with value 3. Now, from here we jump to 5th element with value 9. and from here we will jump to last.
therefore 3 jumps
output=>3
lets use dynamic programming to solve this question:
c++ implementation:
t is the no.of test cases:
lets take an example:
n= 11
a[11]= 1 3 5 8 9 2 6 7 6 8 9
First jump from 1st element, and we jump to 2nd element with value 3. Now, from here we jump to 5th element with value 9. and from here we will jump to last.
therefore 3 jumps
output=>3
lets use dynamic programming to solve this question:
c++ implementation:
t is the no.of test cases:
#include <iostream> #include <bits/stdc++.h> using namespace std; void steps(int a[],int n) { int dp[n]; dp[0]=0; for(int i=1;i<n;i++) { dp[i]=10000; for(int j=0;j<i;j++) { if(j+a[j]>=i) dp[i]=min(dp[i],dp[j]+1); } } if(dp[n-1]==10000) cout<<-1; else cout<<dp[n-1]; } int main() { int t; cin>>t; while(t--) { int n; cin>>n; int a[n]; for(int i=0;i<n;i++) cin>>a[i]; steps(a,n); cout<<endl; } //code return 0; }