Notes on Dynamic Programming
I have been reading about dynamic programming these days. At least to me, dynamic programming appears to be more of a problem solving methodology than a computer programming technique. It is especially effective for certain optimization problems or matching problems, and usually it results in strikingly simple code.
Steps to Design a Dynamic Programming Algorithm
- Design a recurrence that breaks the problem down. (See note below)
- Compute the boundaries.
- Compute the recurrence in such a way that it only refers to values already computed.
Notes on the art of designing a recurrence
Perhaps the most difficult step of dynamic programming is to work out a proper recurrence relationship. In part, I believe that recurrence relationships are problem specific, and the designing or discovering of it is really art. In part, I do find that the form of the recurrence relationship is somewhat correlated with the nature of the problem. In the following section, I attempt to categorize the problems and study the form of the recurrence.
"Linear" Problems vs. Nested Problems
"Linear" problem can be divided into several smaller problems that do not nest each other. The string matching problem is linear because one match between the two strings does not nest other matches. The linear partitioning problem and the largest sum of a run problem are other examples of linear problems.
The solution of such a problem usually has the form S=S1+S2+S3+...+Sn, where Si are partial solutions. Similarly, the cost function of linear problems can often be described as the sum of the cost of a single step and the cost of the rest of the problem.
T(i)=T(i-1,j)+C(j)
A nested problem can be divided into two or more similar sub-problems, each of which can be further divided into sub-problems. Matrix multiplication problem is a typical nested problem. It involves adding parentheses to modify the order of multiplication, and parentheses nest.
The solution of such a problem can typically can be described as a tree that describes the nested relationship of the partial solutions. Similarly, the recurrence relationship can typically be described in the following form:
T(i,j)=T(j,k)+T(k,j)+C(k)
Ordered vs. Non-ordered Problem
Some problems have implicit orders. It is only possible to match sub-strings in the order of their occurrence. Similarly, it is not possible for matrices to exchange places in the matrix multiplication problem. Some problems do not have orders. You can choose any city as your next step in the TSP problem.
For ordered problems, it is usually possible to use only the position of the sequence to describe the partial solutions; for non-ordered problems, however, you will have to use sets to do so. This difference has severe difference in the time complexity of the generated algorithm.
