19. Dynamic Programming 2

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).

练习：

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 是一个基于上个的结果中一个最佳的结果（可能会有多个parents）得出的现有结果的过程。总而言之，是一个由下往上的过程。一旦得到一个结果，那么它在之后的过程中，作为往后计算的基础，一直都不会改变。

最下面的初始化阶段，就是把问题的size减小到最小，得出初始化结果，再慢慢往上走（不断扩大size）。本质上的问题都一样，只是scale不同。

所以，我们只需要确定他的初始化状态，状态转移的条件和状态转移的对象。就可以得出 optimal solution recursively