/*
              Dynamic Programming: Simple Examples



  Consider the naive fibonacci function:

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

  The time complexity of this function is

  T(n) = T(n-1) + T(n-2) + C,

  which is in fact bounded by:

  T(n) = T(n-1) + T(n-1) +C, which we know gives us O(2^n) time. 

  Calling fib(100) will take something on the order of a million years
  to complete.
  
  But now consider a way to optimize this algorithm, without changing its
  mathematical elegance (that is, without changing the way recursion is used).

  The idea is that we use a background array to memorize the result of 
  computing fib numbers, so that redundant computation is avoided.
  For example, the first time we call fib(5), we have to also call
  fib(4) and fib(3).  But then we store the result of fib(5) in the array,
  so that the next time it's needed (such as when fib(6) is called), we
  can return it right away.
*/

using namespace std;
#include<iostream>

/* define the max size of array */
#define SIZE 1000

class dynamicfib
{
public:
  int M[SIZE];
  
  dynamicfib() // constructor initializes matrix
  {
    for (int i=0;i<SIZE;i++) M[i] = -1; 
    // -1 means no value stored here yet
  }

  int dfib(int n)
  {
    if (n<SIZE && M[n]!=-1) return M[n];  // value alread in matrix
    else  // compute value and store in matrix
      {
	int answer = dfib(n-1) + dfib(n-2);
	if (n<SIZE) M[n] = answer;
	return answer;
      }
  } // dfib

  // here's the non-optimized fib for comparison:
  int fib(int n)
  { if (n<2) return 1; else return fib(n-1)+fib(n-2); }
};

int main()
{
  dynamicfib F;
  // cout << F.fib(100) << endl; // uncomment at your own risk
  cout << F.dfib(100) << endl; 
  return 0;
}

/*
   Of course, for the Fibonacci function we don't really need to use
this technique because we can also write it efficiently using a while
loop or tail-recursion and two counter variables.  It's just the
simplest example of dynamic programming.  Why is it "dynamic"?
Because the behavior of the function changes as the program runs.
That is, the first time we call fib(6) is not the same as the second
time we call fib(6), because the second time the function will return
instantaneously. The *static* recurrence T(n)=2*T(n-1)+C no longer
applies to this program.

The time complexity of the new algorithm can be deduced by considering
how the array is "filled up". First we store a value into M[0], then M[1],
M[2], M[3], etc...  Each recursive call to dfib enters a new value into the
array.  The complexity of the new algorithm is O(n) - linear time.
*/

/*
  More complex example:
  Given a grid of size NXM (N rows and M columns) and a coordinate y,x,
  find the number of different "routes" from y,x back to the origin 0,0:
*/

class countroutes
{
public:
  int D[SIZE][SIZE];  
  countroutes()
  {
    for(int i=0;i<SIZE;i++) 
      for(int j=0;j<SIZE;j++) D[i][j] = -1;
  }

  int droutes(int y, int x)
  {
    int answer;
    if (y<SIZE&&x<SIZE && D[y][x]!=-1) answer = D[y][x];
    else 
    {
      if (y==0 || x==0) answer = 1;
      else answer = droutes(y-1,x)+droutes(y,x-1);
      if (y<SIZE&&x<SIZE) D[y][x] = answer;  // remember result
    }
    return answer;
  }

  // solution that doesn't use dynamic programming:
  int routes(int y, int x)
  {
    if (y==0 || x==0) return 1; 
    else return routes(y-1,x)+routes(y,x-1);
  }
};

/*
  The dynamic programming technique can also work on functions that
don't take numerical values.  In such cases, we can use a hash table
instead of a matrix to store the results.  However, dynamic
programming cannot be applied to all problems.  In many cases,
procedures don't return any values at all, and they can behave
differently each time they're called.  Such programs cannot benefit
from this optimization.  But it is a very important programming
technique that is used in many advanced algorithms.
*/