Approaching Dynamic Programming

Question

I have written a small program to calculate the factorial of a number using Dynamic Programming Technique.

#include<stdio.h>

int fact(int n)
{
    int f[n],i;
    f[0] = 1;

    for(i=1;i<=n;i++)
        f[i] = i * f[i-1];
    return f[n];
}

int main(void)
{
    printf("\n Factorial of %d is %d ",5,fact(5));
    return 0;
}

Is the approach of memorization correct? Because, dynamic programming involves recursion. But I have not included it here. So I am not sure of my approach.

Answer 1

Yes, your approach of solving the problem is a very simple case of Dynamic Programming, where you store previously solved sub-problems to help you solve the actual problem. While the example you provided would be considered Dynamic Programming, it usually isn't called Memoization

When someone says Memoization, it usually involves in a top-down approach of solving problems, where you assume you have already solved the sub-problems by structuring your program in a way that will solve sub-problems recursively. You store, or memoize, the results of these sub-problems so that they will not be computed multiple times.

Let me illustrate Memoization through an example:

Here is a simple example of computing the nth Fibonacci of a number:

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

The above code uses recursion to solve sub-problems (fib(n-1) and fib(n-2)) so that fib(n) can be solved in the end. It assumes that fib(n-1) and fib(n-2) are already solved in the way that it is structured.

Though this code looks elegant, the running time is exponential, because you can solve fib(i), where i is a number less than n, multiple times. You can look at the diagram presented here to see the tree generated by this problem: http://www.geeksforgeeks.org/program-for-nth-fibonacci-number.

To avoid the unnecessary re-computation, Memoization is used to optimizes run-time by using memory.

Here is an optimized example of computing the nth Fibonacci number using Memoization:

/*Global array initialized to 0*/
int a[100];

int fib(int n)
{
    /*base case*/
    if (n <= 1) 
        return n;
    /*if fib(n) has not been computed, compute it*/
    if (a[n] == 0) {
        a[n] = fib(n - 1) + fib(n - 2);
    }
    */Otherwise, simply get a[n] and return it*/
    return a[n];
}  

As you can see, the overall structure is not that much different from the recursive solution, but it runs linear time instead of exponential time because fib(i) will only be computed only if we have not computed already.

If I were to use your approach, Dynamic Programming, for the Fibonacci problem, it would look something like this:

 int fib(int n)
 {
   /* just like the array you declared in your solution */
   int f[n+1];
   int i;

   /* set up the base cases, just like how you set f[0] to 1*/
  f[0] = 0;
  f[1] = 1;

   for (i = 2; i <= n; i++)
   {
       /* using previously solved problem to solve further problems*/
       f[i] = f[i-1] + f[i-2];
   }
     /*return the final result*/
   return f[n];
}

There are more subtle differences, trade offs, and implications between Dynamic Programming and Memoization. Some consider Memoization a subset of Dynamic Programming. You can read more about the difference here:

Dynamic programming and memoization: bottom-up vs top-down approaches

Answer 2

Yes this is dynamic programming : going from base cases up to final case. Of course your example (factorial) is too simple so you have been able to simplify many things by yourself : you eliminated the recursion and never use a test in the memoization. But anyway that's it.

For the general scheme of memoization see http://en.wikipedia.org/wiki/Memoization.

For explanation about Dynamic programming see http://en.wikipedia.org/wiki/Dynamic_programming, you will be able to read the section about Fibonacci sequence and its computation using a bottom-up approach.