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;

}



저작자 표시 비영리 변경 금지
신고

'개발/활용정보 > C, C++, C#' 카테고리의 다른 글

dynamic programming  (0) 2013.09.28
zlib 압축  (0) 2011.05.31
C versus C++  (1) 2011.05.31
Trackback 6 And Comment 0