The absolutely indispensable element of dynamic programming
is what we'll call an optimal similar substructure.
By this I mean that we have some hard problems that we want to solve and
we think to ourselves, oh, if I only had the answer to these two similar,
smaller subproblems this would be easy.
And because the subproblems are similar to the original,
we can keep playing this game, letting the problems get smaller and
smaller, until we've reached a trivial case.
Well, at first, this feels like an ideal case for recursion.
Since those subproblems are similar, perhaps we can use the same code and
just change the parameters.
Starting from this hard problem, we could recurse back to this one,
and then to this one, and so
forth using this whole subgraph here to solve this subproblem.
But when we recurse through this branch we would come to this node again and
do all this recomputation again, which would be terribly wasteful.
This is sometimes called one of the perils of recursion.
And it's often illustrated to beginning programmers with the example of
computing the Fibonacci sequence.
Each number in the Fibonacci sequence is the sum of the previous two numbers, and
the first two numbers are one to get us started.
This hard problem of computing the nth number in the sequence depends on
solving the slightly easier problems of computing the n-1 and
the n-2 elements in the sequence.
Figuring out n-1 depends on n-2 as well as n-3.
N-2 depends on knowing the answer to n-3 and n-4, and so forth.
Thinking about how the recursion will operate here,
notice that we need to compute Fn-2 once for Fn, and once also for Fn-1.
So there's going to be some repeated computation here, and
it's going to get worse and worse the further to the left we go.
How bad does it get?
Well, the top-level problem of computing the nth number will only be called once,
and here we'll call the f-1 subproblem once as well.
Computing S of n- 2 needs to happen once for
each time that the 2 computations that depend on it are called.
Once for n- 1 and once for n.
Similarly, n -3 needs to be called once for
every time that the subproblems that depend on it are called.
Twice for Fn-2 and once for Sn-1 for a total of 3.
Fn-4 gets computed once for each time that Fn0-3 is called and
once for each time that Fn-2 is called for a total of 5.
Notice that each number here is the sum of the two numbers to the right.
So this actually is the Fibonacci sequence, and the number of the times
that the n-kth number is computed will be equal to the kth Fibonacci number,
which is roughly the golden ratio raised to the kth power.
So yikes!
This recursive strategy is exponential.
Of course, computing the Fibonacci numbers doesn't need to be exponential.
We could just start on the left here,
initializing the first two numbers to 1 and 1.
And then,
compute the next one as the sum of the previous two with a simple for loop.
There are two ways to cope with this problem of repeated computation.
One, is to memoized the answer to the subproblems.
After we solve it the first time we write ourselves a memo with the answer
and before we actually do the work of solving a subproblem
we always check our wall of memos to see if we have the answer already.
So for instance, for this subproblem here I would have memoized it,
written myself a memo to remember that I've already done it.
And so, when I come this path here, I wouldn't redo all this computations.
I'd just look up the answer.
Alternatively, we can solve the subproblems in the right order, so
that any time we want to solve one of these problems we're sure that we
have the answer to its subproblems already.
This can always be done because the dependency relationships
among the subproblems must form a directed graph.
If they're a cycle, then we would have a circular dependence and
the recursion wouldn't work either.
So we just find an appropriate ordering of the subproblems so that all the edges
go left to right, and then we solve the subproblems in left to right order.
This is the approach we'll take for this lesson.
It tends to expose more of the underlying nature of the problem, and
create faster implementations than using recursion and memoizing.