NUHMAN.com

Dynamic Programming (DP) is a powerful technique used to solve problems by breaking them down into smaller subproblems and solving each subproblem only once, storing the results to avoid redundant work. DP can significantly reduce the time complexity of problems that have overlapping subproblems.

There are two primary approaches in Dynamic Programming:

1. Memoization – A top-down approach where you store results of subproblems as you go along to avoid redundant calculations.
2. Tabulation – A bottom-up approach where you solve all subproblems iteratively and store the results in a table.

In this article, we will explore both techniques and show how they can be implemented in Python.

1️⃣ Memoization (Top-Down Approach)

Memoization involves storing the results of expensive function calls and reusing them when the same inputs occur again. It’s typically implemented using a recursive approach and a cache (often a dictionary or a list).

Memoization Algorithm:

1. Solve the subproblem recursively.
2. Store the result of each subproblem in a cache (e.g., a dictionary or list).
3. If the same subproblem is encountered again, retrieve the result from the cache instead of recomputing it.

Python Code (Fibonacci Example):

python

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]

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

Time Complexity:

• O(n) – Each subproblem is computed once and stored.

2️⃣ Tabulation (Bottom-Up Approach)

Tabulation involves solving all the subproblems iteratively and storing the results in a table (usually an array). This method avoids the overhead of recursion and is often more space-efficient.

Tabulation Algorithm:

1. Create a table (array or list) to store the results of subproblems.
2. Start solving from the smallest subproblem and iteratively build up to the final solution.
3. Use previously computed results to solve larger subproblems.

Python Code (Fibonacci Example):

python

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]

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

Time Complexity:

• O(n) – Each subproblem is computed once and stored.

3️⃣ Comparison of Memoization and Tabulation

TechniqueApproachMemory UsageTime ComplexityMemoizationTop-DownO(n)O(n)TabulationBottom-UpO(n)O(n)

Both techniques reduce time complexity by solving each subproblem only once, but tabulation tends to be more space-efficient in some cases due to its iterative nature.

📝 Common Dynamic Programming Problems

1. Climbing Stairs (LeetCode #70)

Given a staircase with n steps, you can climb 1 or 2 steps at a time. How many ways can you reach the top?

• Memoization Solution:

python

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

• Tabulation Solution:

python

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

2. Longest Increasing Subsequence (LeetCode #300)

Find the length of the longest increasing subsequence in an array.

• Memoization Solution:

python

def length_of_lis_memo(nums, prev_idx=-1, memo={}):
    if prev_idx >= len(nums):
        return 0
    if (prev_idx, len(nums)) in memo:
        return memo[(prev_idx, len(nums))]
    take = 0
    if prev_idx == -1 or nums[prev_idx] < nums[len(nums)]:
        take = 1 + length_of_lis_memo(nums, len(nums), memo)
    skip = length_of_lis_memo(nums, prev_idx + 1, memo)
    memo[(prev_idx, len(nums))] = max(take, skip)
    return memo[(prev_idx, len(nums))]

📝 Summary

ProblemMemoizationTabulationFibonacci SequenceO(n)O(n)Climbing StairsO(n)O(n)Longest Increasing SubsequenceO(n²)O(n²)

Dynamic Programming is a valuable tool for solving optimization problems, and understanding both memoization and tabulation will allow you to choose the best approach for the problem at hand.