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