Dynamic Programming: Fibonacci Series.

Dynamic programming algorithms are almost always developed in two distinct stages.


1. Formulate the problem recursively. Write down a recursive formula or algorithm for the whole problem in terms of the answers to smaller subproblems. This is the hard part.


2. Build solutions to your recurrence from the bottom up. 
Write an algorithm that starts with the base cases of your recurrence and works its way up to the final solution, by considering intermediate subproblems in the correct order. This stage can be broken down into several smaller, relatively mechanical steps:


(a) Identify the subproblems. 
What are all the different ways can your recursive algorithm call itself, starting with some initial input? For example, the argument to RECFIBO is always an integer between 0 and n.


(b) Analyze space and running time. 
The number of possible distinct subproblems determines the space complexity of your memoized algorithm. To compute the time complexity, add up the running times of all possible subproblems, ignoring the recursive calls. For example, if we already know Fi1 and Fi2 , we can compute Fi in O(1) time, so computing the first n. Fibonacci numbers takes O(n) time.


(c) Choose a data structure to memoize intermediate results. 
For most problems, each recursive subproblem can be identified by a few integers, so you can use a multidimensional array. For some problems, however, a more complicated data structure is required.


(d) Identify dependencies between subproblems. 
Except for the base cases, every recursive subproblem depends on other subproblems—which ones? Draw a picture of your data structure, pick a generic element, and draw arrows from each of the other elements it depends on. Then formalize your picture.


(e) Find a good evaluation order. 
Order the subproblems so that each subproblem comes after the subproblems it depends on. Typically, this means you should consider the base cases first, then the subproblems that depends only on base cases, and so on. More formally, the dependencies you identified in the previous step define a partial order over the subproblems; in this step, you need to find a linear extension of that partial order. Be careful!


(f) Write down the algorithm. 
You know what order to consider the subproblems, and you know how to solve each subproblem. So do that! If your data structure is an array, this usually means writing a few nested for-loops around your original recurrence. You don’t need to do this on homework or exams.


Of course, you have to prove that each of these steps is correct.
If your recurrence is wrong, or if you try to build up answers in the wrong order, your algorithm won’t work