Dynamic Programming

--- https://youtu.be/6z4ePR7YYa8

--- https://en.wikipedia.org/wiki/Dynamic_programming

see divide and conquer

definition dynamic programming is a method for efficiently solving through recursion problems with optimal substructure and overlapping subproblems

definition a problem is said to have an optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems

definition a problem is said to have overlapping subproblems if it can be broken down into subproblems which are reused several times

example

# naive solution that recomputes the same subproblems several times

def fib(n):
  return n if n <= 1 else fib(n-1) + fib(n-2)

# dynamic programming solution that memoizes the subproblems

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
  return n if n <= 1 else fib(n-1) + fib(n-2)