<aside> 📌 SUMMARY: Using the dynamic programming approach for Fibonacci numbers allows us to bring the runtime to $O(n)$ instead of being an exponential in $n$. Dynamic programming should have no recursion in its algorithm
</aside>
Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, …
If we use the recursive method, we end up recomputing the same terms many times. This means our runtime is exponential to $n$.
For $n>1$: $F_n=F_{n-1}+F_{n-2}$
Fib1(n)# Recursive solution Fib1(n)
# input: integer n >= 0
# output: Fn
def Fib1(n):
# base cases
if n = 0, return (0) # Takes O(1)
if n = 1, return (1) # Takes O(1)
# Generally
return (Fib1(n-1) + Fib1(n-2)) # recursion, takes T(n-1) + T(n-2)

By using a dynamic programming approach, we instead only incur a long runtime during the loop, which takes at least $O(n)$ — much faster

# DP solution Fib2(n)
def Fib2(n):
F[0] = 0 # O(1), base case
F[1] = 1 # O(1), base case
for i in range(2,n): # For loop takes O(n)
F[i] = F[i-1] + F[i-2] # Each for loop step takes O(1)
return (F[n])
<aside> 📌 SUMMARY: First step in dynamic programming is to define the problem (i.e., $L(i)$) in words. Second step is to find a recurrence relation that the solutions’ sub-problems satisfy. As we were initially unable to do so, we had to reformulate the first step. We strengthen the inductive hypothesis by adding extra conditions that the sub-problem needs to include $a_i$ itself. We could then prove this stronger statement — find the length of the longest sub-sequence with a specific character at the end. By solving this stronger statement, we also solve the weaker statement where we don’t care about the ending character.
</aside>
A subsequence is the subset of the elements in order, and elements in between can be skipped. Note the difference between increasing subsequence and non-decreasing subsequence.
[5, 7, 4, -3, 9, 1, 10, 4, 5, 8, 9, 3][5, 7, 4][5, 7, 9, 10]