public class Memoization {


  public static int fib( int n ) {
  
    if (n < 2) {
      return 1;
    } else {
      return ( fib(n-2) + fib(n-1) );
    }
  }

  public static int fibonacci( int n ) {
  
    return memoization_fib( n, new int[n+1] );
  }

  public static int memoization_fib( int n, int[] history ) {
  
    if ( history[n] == 0 ) {
      if (n < 2) {
        history[n] = 1;
      } else {
        history[n] = ( memoization_fib(n-2,history)
                     + memoization_fib(n-1,history) );
      }
    }
    return history[n];
  }


  public static int manh( int i, int j ) {
  
    if ( (i == 0) || (j == 0) ) {
      return 1;
    } else {
      return ( manh(i-1,j) + manh(i,j-1) );
    }
  }

  public static int manhattan( int i, int j ) {
  
    return memoization_manh( i, j, new int[i+1][j+1] );
  }

  public static int memoization_manh( int i, int j, int[][] history ) {
  
    if ( history[i][j] == 0 ) {
      if ( (i == 0) || (j == 0) ) {
        history[i][j] = 1;
      } else {
        history[i][j] = ( memoization_manh(i-1,j,history)
                        + memoization_manh(i,j-1,history) );
      }
    }
    return history[i][j];
  }
  
  
  public static void main( String[] args ) {
  
    System.out.println( "  Fibonacci(12) :" );
    System.out.println( "  " + fib(12) );
    System.out.println( "  " + fibonacci(12) );
    
    System.out.println( "  Manhattan(5,5) :" );
    System.out.println( "  " + manh(5,5) );
    System.out.println( "  " + manhattan(5,5) );
  }

}