/* The second of three files illustrating dynamic programming.  This 
   one uses recursion but is "memoized" (a dynamic programming idea)
   giving a much faster run time.  */

#include <iostream.h>

#define TMAX 26        /* The number of steps.  */
#define N 2*TMAX+1     /* The "x" size of the A array. */
#define UNCOMPUTED (float) -234 /* There is no way this could be a probability.
                                   It is negative and has magnitude >1.  */


float R( int k, int T, float p, float A[N][TMAX]) {  

  /*  Compute the probability of hitting 0 after T steps, starting
      at k now.  p is the probability that you go from k to k+1.
      1-p is the probability that you go to k-1.            */

   int kindex;
   kindex = k + TMAX; // C arrays all start at 0.  I want FORTRAN!!


//        Here is the memoization step.  Don't recompute if it's known.

   if ( A[ kindex][ T ] != UNCOMPUTED ) return A[ kindex][ T ];

//      At this point in the code, A is not known, use the old algorithm.

   if ( T == 0 ) {  // If at the final time, you know the answer.

      if ( k == 0 ) {
         A[ kindex][ T ] = (float) 1;  // Mark this value as computed.
         return (float) 1; }           // The int -> float conversion may be 
                                       // automatic but let's be safe. 
           
      A[ kindex][ T ] = (float) 0;  // Mark this value as computed.
      return (float) 0;  

   }

 //     If T > 0, compute the consequences of the first step.

   A[ kindex][ T ] = p * R( k+1, T-1, p, A) + ( 1-p ) * R( k-1, T-1, p, A); 
   return A[ kindex][ T ];

}


int main() {

  float A[N][TMAX];
  for ( int k = 0; k < N; k++ ) {
    for ( int t = 0; t < TMAX; t++ ) {
      A[k][t] = UNCOMPUTED; }}


  cout << "Here is a probability computed with memoized recursion... " << endl;
  cout << "   " <<  R( 0, 25, .6, A) << endl;
  cout << "How long did that take?" << endl;

}