Dynamic programming

[Localhost]

Hey, this is my first post here.

Ok, I'm having serious problems learning dynamic programming. In theory I understand it. I know that we need to find a state, or a sub-problem and then find solutions for bigger problems. This is bottom-up. The problem is when I try to find a relation between states. I look at a new problem and then I just don't know how to create that relation.

Any advice? Any starting problems (I couldn't solve any problem until now...)?

Thanks in advance.

[apython1992]

The problem you're mentioning is quite vague, as dynamic programming is a rather broad topic. What kinds of things are you learning right now? That might help me and others to see what you're struggling with.

[A.J]

I recommend looking at various programming text books and trying the USACO training pages. I guess experience plays a huge part in identifying transition states from one sub problem to another; thus solving more problems will be my advice. Try starting off by taking a look into: http://en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming_solution

[SmokeMonster]

Dynamic Programming is incredibly hard, it is probably the hardest I've dealt with so far in CS. I seriously felt stupid in the Dynamic Programming section of my algorithms course.

[A.J]

It sure seems that way at first due to the varying difficulties of problems that usually require DP. However, if you start at the very basics and work your way through examples and contests, you should be able to make good progress. As I mentioned above, when it comes to implementing a dynamic programming algorithm, experience comes into play a lot (as the more experience you have, the better you are in identifying the transition state).

Dynamic programming is one of those topics where it is hard to completely get the message across to a class or even to a CS club. I always told students to participate in contests such as USACO or even sign up on online judges to look for problems that involve Dynamic programming to practice.

[Dratino]

For a good basic example, consider calculating the Fibonacci sequence without a pre-generated sequence.

The recursion F(n) = F(n-1) + F(n-2), if calculated directly, is exponential time (Well, Fibonacci time, which is essentially exponential).

But, if you iterate through finding F(3), then F(4), and so on up the ladder until you reach F(n), it is linear time.

This is an example of some very trivial dynamic programming, at least how I understand it.

*edit* Ah, whoops, you know that already. Silly me >_>

[Brightguy]

Dratino @ Thu Apr 14, 2011 8:30 am wrote:

But, if you iterate through finding F(3), then F(4), and so on up the ladder until you reach F(n), it is linear time.

Linear in the number of arithmetic operations. But still exponential time overall; even just outputting F(n) is exponential time.