Factorials & Fibonacci

[00:00:00]
>> Alright, so we're going to start doing a little bit of dynamic programming because we haven't even covered any dynamic programming have we? Yeah, thank you. The answer is no we haven't. Can you define dynamic programming? Yes, dynamic programming is using past results to compute future values? It's very very simple, so let's just start with a very simple Version of dynamic programming.

[00:00:22]
Factorial of n, right? Wait. That was not n. N factorial! Alright, so there we go, n factorial. To compute n factorial, we could do this the recursive way. I could literally have factorial of n, and so then I just literally return factorial. All real old people are going to be molding because I didn't do a tail recursion right there?

[00:00:50]
Molding, molding in the chat right now you can feel it. So there you go. This would be the recursive solution. Technically, you're still using kind of like past values to calculate future ones. So that's not quite the same. You could imagine you could do the exact same thing with a for loop, right?

[00:01:04]
For i equals one, two n and you just simply sum up the numbers, right? Or whatever it is. You get the idea, I, there you go. And then we return sum. All right, so this would be like the simple conversion from a recursive case to an iterative case and typically this is what you would see when it comes to dynamic programming.

[00:01:25]
Typically it's a recursion to an iterative solution, but you usually reduce the dimensions. There's only one dimension here, nothing actually has changed. So let's go with something with a little bit more interestingness. Let's talk about Fibonacci. So this is like the next most obvious dynamic Programming versus just like your standard approach.

[00:01:44]
If you do your standard Fibonacci solve, what you're going to see is you're going to see this. I'm sure you've all seen this, which is going to be fib (n-1) plus fib (n-2). All right, so the Fibonacci sequence is zero one one two three five eight, gosh 13 can't do math anymore, 21.

[00:02:08]
What you're going to see is that you solve this problem. Now what happens inside of this one? Well this one, what do you solve? Well, you're actually going to solve Fib(n-2) plus fib(n-3), right? That's what you're going to solve right here. Look at this and look at this.

[00:02:28]
You're going to compute that value multiple times. For every single time you go down that tree, you're computing a huge subset of that tree over and and over again. So that is why people don't like to do it this way. It's the cleanest way to do it, but it's also super just not great way to do it.

[00:02:47]
The iterative version of this is you're going to have an a and a b, a will be equal to zero, b will equal to one. You're going to four from this would be one, two, right? So this would be the second number in the solution. So if it's less, if you have two or less, then you just return out the number.

[00:03:04]
So if we're gonna start with three, so that means we have to start at two, going to three. So if i equals three up to n inclusive, by the way, here, we'll go like this. Temp equals b, a, or b equals a plus b, a equals b. Or a equals t.

[00:03:26]
So there we go. We've swapped the two values. That means we went from zero and one for a, to one and one. Then we're going to go from that. Here's a, here's b. We're going to go again, a will become the temporary variable. So, a will remain one, b will become two.

[00:03:42]
Then you're going to have two and you're going to have three, and you're going to just watch that thing kind of count up. So we're no longer, we're using past results to calculate future values.