1. Dynamic Programming typically applies to optimization problems in which a set of choices must be made in order to get an optimal solution
2. As choices are made, subproblems of the same form often arise.

Dynamic programming is effective when the given subproblem may arise from more than one partial set of choices
Therefore, dynamic programming is applicable when the subproblems are not independent.

Four Steps of Developing DP Algorithms

1. Characterize the structure of an optimal solution
2. Define the value of the optimal solution recursively
3. Compute the value of the optimal solution in a bottom-up fashion
4. Construct the optimal solution from the computed information (stored in tables).

Steps 1 - 3 form the basis of a DP solution to an optimization problem

Assembly-line scheduling problem

Each assembly line has n stations. Notation:
Si,j is the jth station in line i
ai, j is the processing time at station Si, j
ti,j is the time to transfer from Si,j to Si', j+1 (i != i')
ei is the entry time for line i
xi is the exit time for line i
i = 1,2 and j = 1,2,...,.

1. Step 1: The structure of the fastest way (optimal solution) through the factory.
   The car must pass through each stage of assembly. Stage j can be reached either from stage j -1 in the same assembly line, or by transferring (with a cost) from stage j -1 in the other assembly line.

2. Step 2:A recursive solution

3. Step 3: Apply the recurrence bottom-up.
   To find the actual shortest path, just record which of the two choices gave the minimum at each step, then work back from the finishing point.

we use an array to memorize from where the value comes.

4. Step 4: Construct the optimal solution
   The array will be used to find the optimal solution

Shortest path in a directed acyclic graph

The way to solve this problem is same to above, here we will calculate the Time complexity.
Suppose that for each vi, we have a list of incoming arcs.

In the worst case we need to look at each node and each arc at least once, so the worst case complexity of the algorithm is theta(n + m).

練習(xí)：

Given a sequence of n elements, find a longest increasing subsequence from the sequence.

Solution:

1. We construct a directed graph G = (V , E ), each element in the sequence is a node in V, there is a directed edge in E from a node vi to another node vj if the element of vi is less than the element vj, and the weight of this directed edge is assigned 1.
2. Clearly, G is a DAG. Then, Add a virtual node v0 and add a directed edge from v0 to v for each v belongs to V, and assign the edge with weight 0. LetG0 bethe final DAG.

Find a longest path in G0 from v0. This path corresponds to the longest increasing subsequence, which takes O(n + m) = O(n^2) time as m = O(n^2)

Personal Consideration about DP

DP 是一個(gè)基于上個(gè)的結(jié)果中一個(gè)最佳的結(jié)果（可能會(huì)有多個(gè)parents）得出的現(xiàn)有結(jié)果的過程。總而言之，是一個(gè)由下往上的過程。一旦得到一個(gè)結(jié)果，那么它在之后的過程中，作為往后計(jì)算的基礎(chǔ)，一直都不會(huì)改變。

最下面的初始化階段，就是把問題的size減小到最小，得出初始化結(jié)果，再慢慢往上走（不斷擴(kuò)大size）。本質(zhì)上的問題都一樣，只是scale不同。

所以，我們只需要確定他的初始化狀態(tài)，狀態(tài)轉(zhuǎn)移的條件和狀態(tài)轉(zhuǎn)移的對(duì)象。就可以得出 optimal solution recursively