analysis on dynamic programming
Personally, I think dynamic programming is very important for a coder. This is not a specific skill but a kind of idea or method of thinking. This helps you get a global optimal result step by step from the easiest condition to the current condition, which is the task we need to solve.
What is Dynamic Programming?
What I have said is just the traits and features of Dynamic Programming, but about the nature of it, we have to state it clearer.
Definition of state is the basis of Dynamic Programming.
State is actually the discrete cases, from the easiest condition to the hardest one, or the cases will not have any order, then we cannot step by step know the next case.
The first step of establishing Dynamic Programming is to define the states of the problem, then we can proceed to connect the states together.
State transform function is the essential element of Dynamic Programming.
State transform function means step by step connection of discrete cases, which is a certain rule or order.
So the second step is to find the connections between the cases, then we can step by step find the result we need.
Some exercise may help for understanding.
I would separate usaco 1.1 and 51nod state 1 later, list all the problems here to make an analysis here, hope you all like it.