# 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 .

-

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)\}$.
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