18.Dynamic Programming 1

引例：

What’s the running time of a naive algorithm for finding an increasing subsequence from a 7-element sequence 5,3,13,6,8,7,10 by enumerating all possible subsequences?

The answer may not be unique, e.g.,
A → B[,,,,,,]
{3,6,7,10}, → {0,1,0,1,0,1,1}
{5,6,7,10}, → {1,0,0,1,0,1,1}
{3,6,8,10}, → {0,1,0,1,1,0,1}
{5,6,8,10}, → {1,0,0,1,1,0,1}
where B[i] = 0 if ai is not in the increasing sequence; otherwise, B[i] = 1. The above naive solution takes O(n · 2^n) time.

Dynamic Programming

Dynamic Programming (DP for short) is a method of solving an optimization problem (a minimization or maximization problem), by first solving some subproblems and then combining the results of subproblems(Divide and Conquer method)

The main requirements for dynamic programming are:

1. The total number of (sub-)subproblems which may occur is fairly small.
2. The solution to each subproblem can be deduced fairly easily from the solutions to the smaller subproblems.

The basic idea of dynamic programming is to solve the subproblems from smallest to largest, storing the solutions in a table

Example

The key observation : any shortest path from {A1,B1} to {An,Bn} consists of a shortest path from {A1,B1} to {An−1,Bn−1} + one more arrow.

1. L[X,Y] = the length of (a directed edge) the arrow from X to Y.
   (eg. L[B2,A3] = 1)
2. P(X) = the length of the shortest path from {A1,B1} to X.

Then, we have this recurrence:

1. P(A1)=0andP(B1)=0
2. For1≤i≤n:
   P(Ai) = min{P(Ai−1) + L[Ai−1, Ai], P(Bi−1) + L[Bi−1, Ai]}
   P(Bi) = min{P(Ai−1) + L[Ai−1, Bi], P(Bi−1) + L[Bi−1, Bi]}

Therefore, the shortest path from {A1,B1} to {A6,B6} has length 8.
The time complexity: O(n)