dynamic programming

https://sites.google.com/site/bauyt008/code--blocks-tips--tricks-and-tutorials/c-dynamic-programming

http://codereview.stackexchange.com/questions/16111/efficient-implementation-of-a-dynamic-programming-problem

----------------

C++ Dynamic Programming

Dynamic Programming * Faster alternatives compared to recursion * In recursion, certain quantities are recalculated far too many times * Need to avoid recalculation, ideally, calculate each unique quantity once * A technique for avoiding recomputation * Can make exponential running times become linear * Store all computed values in an array Source code examples as follows: #include <iostream> using namespace std;   // Factorial bottom-up dynamic programming. // In bottom-up programming, programmer // has to do the thinking by selecting values // to calculate and order of calculation. // This problem is not a good example because // this problem does not exhibit overlapping subproblems // since factorial is called exactly once // for each positive integer less than n. int fact_dp_bu(int n) {     int result[n];     if (n >= 0) {         result[0] = 1;         for(int i=1; i<=n; ++i) {             result[i] = i * result[i-1];         }         return result[n];     }     else {         return numeric_limits<int>::min();     } }   // Factorial top-down dynamic programming // In top-down programming, recursive // structure of original code is preserved, but // unnecessary recalculation is avoided. int factorial[100]; int fact_dp_td(int n) {     if (n < 0)         return numeric_limits<int>::min();       if (factorial[n] > 1)         return factorial[n];       if (n == 0 || n == 1) // base cases first         return 1;       factorial[n] = n * fact_dp_td(n-1);  // recursion case       return factorial[n]; }   /**  *  Computes the factorial of the nonnegative integer n.  *  @pre  n >= 0.  *  @post None.  *  @param n The nonnegative integer to compute its factorial.  *  @return The factorial of n; n is unchanged.  */ int fact_recursion(int n)   // factorial recursion {     if (n == 0)         return 1;                        // base case     else         return n * fact_recursion(n-1);  // n! = n(n-1)!                                          // recursion case }   int fact_iteration(int n)   // factorial iteration {     if (n >= 0) {         int result = 1;         for(int i=1; i<=n; ++i) {             result = result * i;         }         return result;     }     else {         return numeric_limits<int>::min();     } }   // Fibonacci bottom-up dynamic programming. int fibonacci_dp_bu(int n) {     int fib[n];       fib[1] = 1;     fib[2] = 1;       for (int j=3; j<=n; ++j)       fib[j] = fib[j-1] + fib[j-2];       return fib[n]; }   // Fibonacci top-down dynamic programming. // This problem is a good example. // The problem of calculating the nth Fibonacci number does, // however, exhibit overlapping subproblems. // The problem of calculating fib(n) thus depends // on both fib(n-1) and fib(n-2). // To see how these subproblems overlap look at // how many times fib is called and with what arguments // when we try to calculate fib(5): // fib(5) // = fib(4)                   + fib(3) // = fib(3)          + fib(2) + fib(2) + fib(1) // = fib(2) + fib(1) + fib(2) + fib(2) + fib(1) // = 5 // Starting from the bottom and going up we can calculate // the numbers we need for the next step, removing the massive redundancy. int saveFib[100]; int fibonacci_dp_td(int n) {     // simple cases first     if (saveFib[n] > 0)         return saveFib[n];       if (n <= 1)         return n;       // recursion case     saveFib[n] = fibonacci_dp_td(n-1) + fibonacci_dp_td(n-2);       return saveFib[n]; }   /**  * Computes a term in the Fibonacci sequence.  * @pre n is a positive integer.  * @post None.  * @param n The given integer.  * @return The nth Fibonacci number.  */ int fibonacci_recursion(int n) {     if (n <= 2)         return 1;       else         return fibonacci_recursion(n-1) + fibonacci_recursion(n-2); }   // @pre n >= 1 int fibonacci_iteration(int n) {     int previous = 1;     int current = 1;     int next = 1; // result when n is 1 or 2       // compute next values when n >= 3     for (int i = 3; i <= n; ++i) {         next = current + previous;         previous = current;         current = next;     }       return next; }   int main(int argc, char* argv[]) {     cout << fact_dp_bu(5) << endl;     cout << fact_dp_td(5) << endl;     cout << fact_recursion(5) << endl;     cout << fact_iteration(5) << endl;     cout << fibonacci_dp_bu(8) << endl;     cout << fibonacci_dp_td(8) << endl;     cout << fibonacci_recursion(8) << endl;     cout << fibonacci_iteration(8) << endl;       system("PAUSE");     return 0; }