Thursday, June 21, 2012

Dynamic programming

Dynamic programming, or DP for short, can be applied on the problems that could be divided into sub problems. The solution of the entire problem can be found by “combing” the solutions of its sub problem. The main steps of DP can be generalized as follows:

  • define the solution;
  • recursively define the solutions from sub solution;
  • calculate the solution, from bottom to the top;
  • generate a solution based on the sub-solutions.

There are two key points needed to be clarified, before applying DP. The first is optimal substructure and the other one is overlapping sub problems.

  • Optimal substructure, means the substructures of a solution must be also optimal;
  • Overlapping sub problem, means the sub problems, when we recursively decompose the problem, may not be always new problems. For example, some problems may need to be calculated many times. If we could store the result of it, then we could just lookup the result, instead of recalculating. In another world, DP is a method which uses space to reduce time.

Now, let us check a typical DP problem, longest common subsequence(LCS). If you do not know LCS, please Google it.

Suppose there are two string, Xm={x1, x2, x3, …, xm} and Yn={y1, y2, y3, …, yn}. Zk={z1, z2, z3, …, zk} is the X`s, or Y`s, LCS. The elements in LCS need to be in the same order, but not continuous.

Then we could find three properties as follows:

  • if xm-1 == yn-1, then zk-1 = xm-1 == yn-1, and zk-1 is a LCS of Xm-1 and Yn-1;
  • if xm-1 != yn-1, and zk-1 != xm-1, Z is the LCS of xm-1 and Y;
  • if xm-1 != yn-1, and zk-1 != yn-1, Z is the LCS of yn-1 and X;

A recursive solution could be obtained as follows. Suppose c[m][n] denotes the length of the LSC of X[1:m] and Y[1:n].

          / 0, if i<0 and j<0; // case 1 
c[i][j] = | c[i-1][j-1]+1, if i, j >=0 and xi==yj; // case 2
\ max( c[i][j-1]m c[i-1][j] ), if i, j>=0 and xi!=yj; // case 3

After we execute the function above recursively, we could found the length of LCS at c[m][n]. If we want extract the LCS, we need to define anther matrix, D, to store the direction of how each state transited, and define 3 three directions.

  • If D[i][j] holds direction 1, denoted as image, we move next position at D[i-1][j-1];
  • If D[i][j] holds direction 2, denoted as image, we move next position at D[i-1][j];
  • If D[i][j] holds direction 3, denoted as image ,we move next position at D[i][j-1];

Those three directions correspond to the conditions in the case 2 and 3 in the function. A trace back function as followed could be used to print the LCS. Suppose b is one string, X is the direction map and (i, j) is the index of X.


No comments:

Post a Comment