system
Given the following post, respond as if you're commenting on Reddit:
human
ELI5 what is dynamic programming?

I’ve been encountering problems lately where the solution requires a dynamic programming solution, but I can’t wrap my head around how that works. Can some ELI5 it?
gpt
Dynamic programming is a way of breaking problems up into repeated subproblems, then solving the subproblems from the bottom up, reusing any answers that you’ve already figured out. 

Consider a naive recursive Fibonacci function:

```
fib(0) = 0
fib(1) = 1
fib(n) = fib(n - 1) + fib(n - 2)
```
I’m on mobile so I’ll use notation “fn” to mean `fib(n)`. 

f5 = f4 + f3 

f5 = (f3 + f2) + f3

Now I’ll expand the f3 calls.

f5 = ((f2 + f1) + f2) + (f2 + f1)

Now I’ll expand all the f2 calls. 

f5 = (((f1 + f0) + f1) + (f1 + f0)) + ((f1 + f0) + f1)

Now let’s look at how many times fib got called. 

-	f0: 3 times
-	f1: 5 times
-	f2: 3 times
-	f3: 2 times

For f0 and f1, this isn’t a huge deal. But we had to calculate f2 twice more than necessary and f3 once more than necessary. This is ok for `fib(5)` but it won’t be ok for `fib(100)`.

Since the nth Fibonacci number builds on the last two,  and this logic will unroll all the way down to 1, we should only need to calculate fx once for each x less than n.

```
fib_dynamic(n):
  if n is 1 or 0 return n
  fibs = [0, 1] // fibs[x] represents the xth Fibonacci number
  for i from 2 to n, inclusive:
    fibs[i] = fibs[i - 1] + fibs[i - 2]
  return fibs[i]
```

Try out fib_dynamic(5) on pen and paper and see the difference. 

With this method, we don’t have to repeat any work because we saved the intermediate answers to be used again. 

There exists another technique very similar to dynamic programming, called *memoization* (yes, that’s how you spell it), where you essentially save the results of each function call, then the next time that function is called with the same arguments you can return the saved version. This is often a little bit easier to implement because you don’t have to change your algorithm to go bottom-up, the stack will do it for you.

```
cache = [0, 1]
fib_memo(n):
  if cache[n] exists, return it
  cache[n] = fib_memo(n - 1) + fib_memo(n - 2)
  return cache[n]
```

Try this one out on pen and paper too, see how it compares to the other two.