Minimum Jumps to Reach end of Array

bottom up approach.cpp

// https://www.youtube.com/watch?v=BH9HKqMfKEU

int bottomUp(int arr[] , int n){
    int mem[100] = {0} ; 
    mem[0] = 0 ; 

    for(int i =1 ;i < n ; i++){
        int minvalue = INT_MAX;
        int minIndex =-1;

       for(int j=0 ;j<i ;j++) {
          if(arr[j]+j >= i){
              if(mem[j] < minvalue){
                minIndex = j; 
              }
              minvalue = min(minvalue , mem[j]);
          }
       }
      
       if(minvalue!=INT_MAX){
        mem[i] = minvalue+1;
       }
       else mem[i] = INT_MAX;
    }
    cout<<endl;
    return mem[n-1];
}

O(N) time , O(1) space optimal.cpp

int solve(int arr[] , int n ){
    int maxReachable , jumps  , stepsPossible ;  

    maxReachable = arr[0] ; 
    jumps = 1 ; 
    stepsPossible = arr[0] ; 

    for(int i = 1 ; i<n ; i++){
        if(i==n-1) return jumps ;  
        
        maxReachable = max(maxReachable , i+arr[i]);

        stepsPossible-- ; 

        if(stepsPossible==0){
            jumps++ ; 
            if(i>=maxReachable) return -1;
            stepsPossible = maxReachable - i ; 
        }
    }

}


int main(void){
    int N = 11 ; 
    int arr[100] = {1,3,5,8,9,2,6,7,6,8,9};
    cout<<solve(arr,N) <<endl;
}

top down approach.cpp

// https://www.youtube.com/watch?v=hGVDAQAuJnI&t=216s

int solveTopDown( int i  , int arr[] , int n){
    if(mem[i]>0) return mem[i] ; 
    if(i>=n) return  INT_MAX ; 
    if(i==n-1) return 0;

    int steps = arr[i] ;
    int minvalue = INT_MAX ; 
    
    for(int j=1 ; j<=steps ;j++){
        minvalue = min(minvalue ,solveTopDown(i+j , arr , n));
    }
    mem[i] =  minvalue + 1 ; 
    return mem[i] ; 
}


int main(void){
    int N = 11 ; 
    int arr[100] = {1,3,5,8,9,2,6,7,6,8,9};
    cout<<solveTopDown(0 , arr , N) <<endl; 
}

add a test case : if(arr[0] == 0) return -1;