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! :confused: Looking for something a little less complicated to sink my teeth into...

What do you mean by 'dynamic programming'?

Sounds interesting...

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

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

Try placing a post on the discussion board at

www.generation5.org

I think this board would be more relevant for you.

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

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.

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...:confused:

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.