Optimization Techniques in Algorithms: Dynamic Programming

What is Optimization in Algorithms?

Optimization techniques help improve the efficiency of algorithms by reducing time and space complexity while maintaining correctness of results.

Dynamic Programming (DP)

DP is a powerful optimization approach designed to solve problems exhibiting overlapping subproblems and optimal substructure by storing intermediate results to avoid redundant computations.

Two Primary Techniques of Dynamic Programming

Technique	Description	Approach	Strength
Memoization	Top-down recursion with caching of intermediate results.	Recursive	Simple implementation when recursion is natural.
Tabulation	Bottom-up iterative filling of a DP table.	Iterative	Often more efficient, no recursion overhead.

Example: Fibonacci Number using Memoization

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

print(fib_memo(10))  # Output: 55

Example: Fibonacci Number using Tabulation

def fib_tab(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 Optimization Techniques?

Use when naive or recursive solutions have exponential time.
Problems exhibiting overlapping subproblems and optimal substructure.
To transform exponential solutions into polynomial-time algorithms.