Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 .

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.