What is dynamic programming?

Dynamic Programming (DP) is an algorithmic technique for solving complex problems by breaking them down into simpler subproblems. It solves each subproblem only once and stores the results, typically to avoid redundant computations when the same subproblem occurs multiple times.

What is Dynamic Programming?

Dynamic Programming is a powerful method used in computer science and mathematics, particularly in optimization problems. It's applicable to problems that can be divided into smaller, independent subproblems whose solutions can be combined to solve the overall problem. The two main properties that characterize a problem solvable by Dynamic Programming are Overlapping Subproblems and Optimal Substructure.

Key Characteristics

• Overlapping Subproblems: The problem can be broken down into subproblems that are reused multiple times. Instead of recomputing solutions to these subproblems, DP stores their results.
• Optimal Substructure: An optimal solution to the overall problem can be constructed from optimal solutions of its subproblems.

Two Main Approaches

• Memoization (Top-down): This approach starts from the original problem and recursively breaks it down into subproblems. It stores the results of solved subproblems in a data structure (like a hash map or array) to avoid re-computation. When a subproblem is encountered, it first checks if its solution is already computed and stored.
• Tabulation (Bottom-up): This approach solves subproblems in a systematic order, typically starting from the smallest subproblems and building up solutions to larger ones. It fills up a table (usually an array) with the solutions to subproblems, ensuring that when a larger subproblem needs a smaller subproblem's solution, it's already available.

Example: Fibonacci Sequence

The Fibonacci sequence (0, 1, 1, 2, 3, 5, 8, ...) is a classic example to illustrate dynamic programming. A naive recursive implementation recomputes the same Fibonacci numbers many times, leading to exponential time complexity. DP significantly improves this.

Memoization (Top-down) for Fibonacci

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

# print(fib_memo(10)) # Output: 55

Tabulation (Bottom-up) for Fibonacci

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

# print(fib_tab(10)) # Output: 55

When to Use Dynamic Programming

• Optimization problems (finding the minimum, maximum, shortest path, longest subsequence, etc.)
• Problems exhibiting Overlapping Subproblems and Optimal Substructure.
• Often used in algorithm challenges and real-world scenarios like pathfinding, resource allocation, and sequence alignment.