https://leetcode.com/discuss/study-guide/662866/DP-for-Beginners-Problems-or-Patterns-or-Sample-Solutions
it is commonly an optimization over recursion.

dynamic programming is a way to make algs more efficient by storing in memory the result of some previous computation that is otherwise repeated many times.

There are 2 techniques that follow this way of solving a problem:

memoization

Also called top down approach.
Most commonly known or used than the other. this technique of storing previously computated value in a cache is called memoizatoin.

In this approach, you solve the problem by breaking it down into subproblems and storing the results of these subproblems in a table (usually an array or a dictionary) to avoid redundant calculations.

• Recursive: The problem is solved recursively, and intermediate results are stored to ensure each subproblem is solved only once.
• Use Case: Useful when the problem has an inherent recursive structure.

here is an example of memoization in a fibonacci function:

# A simple example of a recursive Fibonacci function with memoization

# Memoization cache
fib_cache = {} #dictionary

def fibonacci(n):
    # Check if value is in cache
    if n in fib_cache:
        return fib_cache[n]
    
    # Base case
    if n == 0:
        value = 0
    elif n == 1:
        value = 1
    else:
        # Recursive case
        value = fibonacci(n-1) + fibonacci(n-2)
    
    # Store the value in the cache and return it
    fib_cache[n] = value
    return value

# Test the function
print(fibonacci(10))  # Output: 55

def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 2:
        return 1
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

print(fib_memo(10))

tabulation

Also called bottom up approach.
You solve the problem by starting with the smallest subproblems and iteratively solving larger subproblems based on the results of the smaller ones.

• Iterative: The problem is solved iteratively, and results of subproblems are stored in a table, which is filled in a specific order.
• Use Case: Efficient in terms of space and sometimes preferred when the problem doesn't naturally lend itself to a recursive solution.
  May be more complex to implement, as it requires careful planning of the order in which subproblems are solved.

def fib_tab(n):
    if n <= 2:
        return 1
    dp = [0] * (n + 1)
    dp[1] = dp[2] = 1
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

print(fib_tab(10))