If we solve it naively, complexity will be O(1.6^n).
Now we can solve it in DP using two ways:
1. Top Down: Instead of recursively computing the same subproblem, just store the value of this computation and look it up when needed. That's it.
2. Bottom Up: One cannot come up with bottom up representation directly, unless we identify its recursive pattern and subproblems. Once we have this recursive pattern, just plot a graph for some values and we can identify overlapping subproblem and its overall graph.
Constructing graph for fib(5), we can see solutions from fib(4) and fib(3) are needed. Therefore, we need to find fib(3) and fib(4) before even solving for fib(5). Once we identify this graph, we can do bottom up, where we solve base solution (trivial or first node in graph) and construct our solution based in it.
Therefore, easy approach is to solve it top-down. Once it is done, we can identify subproblem graph and construct bottom up solution.
This is all well and good for fibonacci but it feels like the difficulty of the problem becomes exponentially greater when you start running into more complicated optimization strategies. Text justification is an example:
Consider Fibonacci sequence: f(0) = 0; f(1) = 1; f(n) = f(n-1) + f(n-2)
If we solve it naively, complexity will be O(1.6^n).
Now we can solve it in DP using two ways:
1. Top Down: Instead of recursively computing the same subproblem, just store the value of this computation and look it up when needed. That's it.
2. Bottom Up: One cannot come up with bottom up representation directly, unless we identify its recursive pattern and subproblems. Once we have this recursive pattern, just plot a graph for some values and we can identify overlapping subproblem and its overall graph.
Constructing graph for fib(5), we can see solutions from fib(4) and fib(3) are needed. Therefore, we need to find fib(3) and fib(4) before even solving for fib(5). Once we identify this graph, we can do bottom up, where we solve base solution (trivial or first node in graph) and construct our solution based in it.
Therefore, easy approach is to solve it top-down. Once it is done, we can identify subproblem graph and construct bottom up solution.