Dynamic programming in C++

This is a discussion on Dynamic programming in C++ within the C++ Programming forums, part of the General Programming Boards category; Anyone know of a good website that talks about dynamic programming for C++ in depth? All of my google searches ...

  1. #1
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728

    Dynamic programming in C++

    Anyone know of a good website that talks about dynamic programming for C++ in depth? All of my google searches so far have only provided me with incomplete webpages or explanations meant for people with PhD's in mathematics. I'm OK at math but nowhere near at this level! Looking for something a little less complicated to sink my teeth into...

  2. #2
    Code Monkey Davros's Avatar
    Join Date
    Jun 2002
    Posts
    812
    What do you mean by 'dynamic programming'?

    Sounds interesting...

  3. #3
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    I'm not sure on the official definition, but it has to do with mathematics to solve problems in a simpler way than brute force. Like for instance solving the 50th fibocacci number without making a 50 deep recursive function. Errr... its hard to describe although I know they teach it to many CS students in algorithm classes and you DEFINATELY need to know it to do well at something like topcoder.com

  4. #4
    Registered User
    Join Date
    Nov 2001
    Posts
    1,348
    I believe you will learn more about dynamic programming via books and college courses than do you will from tutorials. The subject involves extreme high-level math and mathematically theories.

    Kuphryn

  5. #5
    Code Monkey Davros's Avatar
    Join Date
    Jun 2002
    Posts
    812
    Try placing a post on the discussion board at

    www.generation5.org

    I think this board would be more relevant for you.

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    Okay, consider two ways of dynamic programming:

    Top-down: Using this technique you avoid intense processing (such as an exponential recursive time recursive function) by saving known values so that you don't have to recalculate them.

    Bottom-up: With this method, instead of saving known values, you precompute them

    Using the Fibonacci example, here is the bad version:
    Code:
    int fib ( int i )
    {
      if ( i < 1 )
        return 0;
      if ( i == 1 )
        return 1;
      return fib ( i - 1 ) + fib ( i - 2 );
    }
    Using a Bottom-up method, the exponential time of the fib function was cut down to linear simply by simply by computing the first N numbers and storing them in a global array, the function avoids recomputing values.
    Code:
    int pre[45];
    
    int fib ( int i )
    {
      int t;
    
      if ( pre[i] != 0 )
        return pre[i];
      else if ( i == 0 )
        t = 0;
      else if ( i == 1 )
        t = 1;
      else if ( i > 1 )
        t = fib ( i - 1 ) + fib ( i - 2 );
    
      return pre[i] = t;
    }
    -Prelude
    My best code is written with the delete key.

  7. #7
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    Dynamic programming was
    created before computers by social enginneers. So
    dynamic and programming have nothing to do with
    programming. It refers to a tabular method of computation.
    The scope of problems that can be solved must form a
    optimization heiarchy, which means basically you
    can find the optimal method by looking at the solution of
    the subproblems. http://mat.gsia.cmu.edu/classes/dynamic/dynamic.html
    Also algorithms by Cormen et al has a pretty long section
    on this. Another thing you might want to look into is memoization.

  8. #8
    Cheesy Poofs! PJYelton's Avatar
    Join Date
    Sep 2002
    Location
    Boulder
    Posts
    1,728
    Thanks all, I'll look more into all of this starting with a bookstore. One question that baffles me though, why all the fuss over fibonacci numbers to such an extent that they are trying to solve them using recursion and dynamic programming?? I can do it with a simple for loop:
    Code:
    // x and y are the first two numbers, z is the number out to
    vector<int> vec;
    vec.push_back(x);
    vec.push_back(y);
    for (int i=2; i<z; i++)
         vec.push_back(vec[i-1]+vec[i-2]);
    
    return vec[z-1];
    This can be done no matter what the first two numbers are or even if you want to do special fibo's like summing up the last three, etc, AND its faster! I guess I just don't understand the fuss...

  9. #9
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    Well you can do it with 2 state variables and there's an
    actual formula that calculates it. fib with arrays is more of a technique of memoization. You use this technique when you notice that there is alot of overlap
    in the calculation. Another example
    of memoization is calculating Ackermann's function.
    http://pw1.netcom.com/~hjsmith/Ackerman/AckeWhat.html
    Basically you can create a static 2d array and see if the results are
    in the table and if they are not you calculated it.

    Dynamic Programming, at least the way my book defines
    it is a little bit different because it is used more in algorithms
    where your trying to find an optimal solution. When you design
    the algorithm you create a recursive definition, but the actual
    implementation would just use a loop.
    For example here's fib again

    Code:
    int fib(int n)
    {
        int f[N];
        int i;
    
        f[0] = 1;
        f[1] = 1;
    
        for (i = 2; i <= n; ++i)
            f[i] = f[i-1] + f[i-2];
    
        return f[n];
    }
    Another comon dynamic programming problem is the
    knapsack problem.
    Introduction to Algorithms by Cormen et al is a good book
    that covers all this.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 07-11-2008, 08:39 AM
  2. dynamic array/vector help
    By Cpro in forum C++ Programming
    Replies: 8
    Last Post: 04-05-2008, 04:30 PM
  3. Identify dynamic IP address of network device
    By BobS0327 in forum Tech Board
    Replies: 2
    Last Post: 02-21-2006, 01:49 PM
  4. operator overloading and dynamic memory program
    By jlmac2001 in forum C++ Programming
    Replies: 3
    Last Post: 04-07-2003, 12:51 AM
  5. Dynamic memory confusion
    By ripper079 in forum C++ Programming
    Replies: 5
    Last Post: 11-04-2002, 06:15 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21