pastebin

Paste Search Dynamic
Recent pastes
find_jump
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int min(int a,int b){
  5.         if(a>=b)
  6.         return b;
  7.         else
  8.         return a;
  9.        
  10. }
  11.  
  12. int find_jump(int arr[], int n)
  13. {
  14.     //n=input1;
  15.     int k=0;
  16.     int* path = new int[n];
  17.     int i, j;
  18.  
  19.     if (n == 0 )
  20.         return int_max;
  21.     if (arr[0] == 0)
  22.     return int_max;
  23.     path[0] = 0;
  24.     for (i = 1; i < n; i++) {
  25.         path[i] = int_max;
  26.         for (j = 0; j < i; j++) {
  27.             if (path[j] != int_max && i <= j + arr[j]) {
  28.                 path[i] = min(path[i], path[j] + 1);
  29.                 k=1;
  30.                 break;
  31.             }
  32.         }
  33.     } if(k==0)
  34.     return -1;
  35.     else
  36.     return path[n - 1];
  37. }
  38.  
  39.  
  40.  
  41.  
  42.  
  43. int main() {
  44.         // your code goes here
  45.         int n;
  46.         cin>>n;
  47.         int arr[n];
  48.         for(int i=0;i<n;i++)
  49.         cin>>arr[i];
  50.        
  51.         if(n==1){
  52.                         cout<<"0";
  53.                         exit(0);
  54.         }
  55.        
  56.         int k=find_jump(arr,n);
  57.         cout<<k;
  58.         return 0;
  59. }
Parsed in 0.013 seconds