0
$\begingroup$

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 Answers 1

4

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.

  • 0
    I see now . thanks .2012-09-05