# What is a subproblem graph in dynamic programming parlance?

I know what dynamic programming is but I do not really understand the concept of subproblem graph for a dynamic programming ? How are they useful ? When solving problem by dynamic programming should I think in terms of subproblem graphs ? Does it tell anything about time complexity of our algorithm (may be give us some idea in terms of Big O ) ?

I know finding the nth Fibonacci number can be solved by dynamic programming . Can some one explain the subproblem graph for Fibonacci sequence as an example . You can use other examples also if you like .

-

## 1 Answer

A subproblem graph is used to indicate the dependencies between the various subproblems. Each node in the graph represents a particular subproblem and edges between subproblems indicates dependencies. For example, if $C(5)=2C(4) + C(3)$ where $C(i)$ denotes the $i^{th}$ subproblem then the subproblem graph would have edges $\{C(5),C(4)\}$ and $\{C(5),C(3)\}$.

They are useful in designing dynamic programming schemes. They are also useful in determining the run-time of a dynamic programming algorithm once a solution scheme has been set. In dynamic programming the goal is to minimize the number of times you compute the same subproblem - ideally you want to solve a subproblem at most once.

-
I think you meant $\{C(5),C(4)\}$ and $\{C(4),C(3)\}$ or am I missing something here ? –  Geek Sep 5 '12 at 14:43
I really did mean the two edges I posted. In order to compute the value of $C(5)$ you need to know the answers of $C(4)$ and $C(3)$. That is what is meant by "subproblem dependency", i.e., the subproblem $C(5)$ depends on the subproblems $C(4)$ and $C(3)$. –  shoda Sep 5 '12 at 14:53
I see now . thanks . –  Geek Sep 5 '12 at 14:55