What is dynamic programming?

Dynamic programming (DP) is a method for solving complex computational problems by breaking them down into simpler subproblems. The results of these subproblems are stored (memoization or tabulation) to avoid redundant calculations. This allows for significant optimization compared to naive recursive solutions.

Main principles:

• Overlapping subproblems: The same subproblem must be solved multiple times when solving the original problem.
• Optimal substructure: The optimal solution to the original problem can be derived from the optimal solutions of its subproblems.

Two main approaches:

1. Top-down (memoization): Uses recursion with memoization. The problem is broken down into subproblems, and their solutions are stored in a dictionary or array.
2. Bottom-up (tabulation): Uses an iterative approach with tabulation. Subproblem solutions are computed in a specific order (usually from smaller to larger) and stored in a table.

Example. Fibonacci number problem:

Naive recursive solution (without DP):

def fibonacci_naive(n):
    if n <= 1:
        return n
    else:
        return fibonacci_naive(n - 1) + fibonacci_naive(n - 2) # Repeated calculations of the same value

DP solution (memoization):

def fibonacci_memoization(n, memo={}):
    if n in memo:
        return memo[n] # Return stored result
    if n <= 1:
        return n
    else:
        result = fibonacci_memoization(n - 1, memo) + fibonacci_memoization(n - 2, memo)
        memo[n] = result # Store result
        return result

DP solution (tabulation):

def fibonacci_tabulation(n):
    if n <= 1:
        return n
    
    dp = [0] * (n + 1) # Table to store results
    dp[0] = 0
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2] # Compute based on previous results

    return dp[n]

Differences between memoization and tabulation:

Parameter	Memoization (Top-down)	Tabulation (Bottom-up)
Approach	Recursive	Iterative
Order	Computations depend on the request	Computations in a predefined order
Memory	May use more memory (stack)	Usually uses a fixed array/table
Implementation	Can be simpler for some problems	Usually more efficient in memory and speed

DP is applied in various fields, including:

• Optimization: knapsack problem, traveling salesman problem.
• Bioinformatics: DNA sequence alignment.
• Computer vision: pattern recognition.
• Finance: investment planning.