Dynamic Programming: Mantras - mbhushan/dynpro GitHub Wiki

Mantra: Soul of DP

Every dynamic program has an underlying dag structure: think of each node 
as representing a subproblem, and each edge as a precedence constraint on 
the order in which the subproblems can be tackled. Having nodes u1.....uk 
point to v means “subproblem v can only be solved
once the answers to u1....uk are known.”

Mantra: Common subproblems - FOUR FOLD PATHS

Finding the right subproblem takes creativity and experimentation. 
But there are a few standard choices that seem to arise repeatedly 
in dynamic programming.

i. The input is x1; x2; : : : ; xn and a 
subproblem is x1; x2; : : : ; xi.

x1 x2 x3 x4 x5 x6 x7 x8 x9 x10

The number of subproblems is therefore linear.

==============================================================================================

ii. The input is x1; : : : ; xn, and y1; : : : ; ym. A subproblem 
is x1; : : : ; xi and y1; : : : ; yj.

x1 x2 x3 x4 x5 x6 x7 x8 x9 x10

y1 y2 y3 y4 y5 y6 y7 y8

The number of subproblems is O(m*n).

==============================================================================================

iii. The input is x1; : : : ; xn and a subproblem 
is xi; xi+1; : : : ; xj .

x1 x2 x3 x4 x5 x6 x7 x8 x9 x10

The number of subproblems is O(n^2).

==============================================================================================

iv. The input is a rooted tree. A subproblem is a rooted subtree.

If the tree has n nodes, how many subproblems are there?