Basic Concept
Some Questions
-
1: If we want to solve one problem, what information do we need to have?
-
2: How can we use as few as information to get the answer of the problem?
-
3: How can we change the information, that we're hard to get, to the inforemation that we're easy to get?
-
- How can we use the limited memory to store informations as much as we can? ( Memoried search also can give help to this problem )
The Condition
-
We can sort the condition into more and more small condition. The process that we sort the condition is called "divide-and-conquer".
-
The judge of condition is the most basic thing of DP. So, the every possible route that we are able to meet, we called it "condition".
-
The new condition is get by update the old condition. For exanple, while we need
f[x], we may needf[x - 1]orf[x - 2]or both or more.
The Transfer
-
State transfer equation means, the old condition how to transfer to the new one.
-
You can simplely thought that state-transfer-equation is a rule, to guide the code how to calculate the right answer.
Small Summary
-
To see the two part before, we can make a summary:
-
First of all, we need to design a condition. We use condition to show every problem.
-
Secondly, we write the state-transfer-equation, use the small problem's solution to get the big problem's solution.
-
Some Skip
-
While you are thinking about state-transfer-equation, you can think about: where should I go in the next step? This question can help you solve DP problem. We called this kind of thought "push".
-
Opposite of the thought before, "pull" thought is think where did I come. These two thought both can help you.
Who I am?
Where did I come?
Where should I go?
- You should ask yourself these questions when you solve DP.
