Overview

  • Dynamic Programming (DP) is a method for solving problems by breaking them into smaller overlapping subproblems.
  • It stores the results of subproblems to avoid redundant computation (memoization) or iteratively builds up solutions (tabulation).
  • Ideal for optimization problems and problems with overlapping subproblems and optimal substructure.

Key Concepts

  1. Overlapping Subproblems

    • The problem can be divided into subproblems that are solved multiple times.

  2. Optimal Substructure

    • The solution to the problem can be composed of solutions to its subproblems.

  3. Memoization vs Tabulation

    • Memoization: Top-down approach using recursion and caching results.
    • Tabulation: Bottom-up approach building the solution iteratively in a table.

Steps to Solve DP Problems

  1. Define the state:
    • Decide on variables that represent subproblem states.
  2. Write the recurrence relation:
    • Formulate the relationship between the current state and its subproblems.
  3. Identify the base cases:
    • Define the smallest subproblems and their solutions.
  4. Decide between memoization or tabulation.
  5. Optimize (optional):
    • Space and time optimizations, if applicable.

Example Problems

1. Fibonacci Numbers

Compute the nth Fibonacci number.

Recurrence Relation

F(n) = F(n-1) + F(n-2)

Implementation

Memoization:

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

print(fib_memo(10))  # Output: 55

Tabulation:

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

2. 0/1 Knapsack Problem

Given weights and values of items, maximize the total value without exceeding a weight limit.

Recurrence Relation

Let dp[i][w] = max value for first i items with a weight limit of w.

  • dp[i][w] = dp[i-1][w] if weight[i] > w
  • dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w-weight[i]]) otherwise

Implementation

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i-1] > w:
                dp[i][w] = dp[i-1][w]
            else:
                dp[i][w] = max(dp[i-1][w], values[i-1] + dp[i-1][w - weights[i-1]])

    return dp[n][capacity]

# Example Usage
weights = [1, 2, 3]
values = [10, 15, 40]
capacity = 6
print(knapsack(weights, values, capacity))  # Output: 55

3. Longest Increasing Subsequence (LIS)

Find the length of the longest subsequence in an array that is strictly increasing.

Recurrence Relation

Let dp[i] = LIS ending at index i.

  • dp[i] = max(dp[j] + 1 for all j < i if arr[j] < arr[i])

Implementation

def lis(nums):
    n = len(nums)
    dp = [1] * n

    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

# Example Usage
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(lis(nums))  # Output: 4

Common DP Problems

Subset Sum

  • Given a set of integers, determine if a subset sums up to a given target.

Longest Common Subsequence (LCS)

  • Find the longest subsequence present in both strings.

Edit Distance

  • Calculate the minimum number of operations to convert one string to another.

Matrix Chain Multiplication

  • Determine the optimal way to multiply matrices to minimize operations.

Coin Change

  • Find the minimum number of coins required to make up a given amount.

Unique Paths

  • Find the number of unique paths in an m x n grid.

Optimization Techniques

  1. Space Optimization

    • Reduce space complexity by storing only necessary states.
    • Example: For Fibonacci, only keep the last two values instead of a full array.

  2. Bitmasking

    • Useful for problems involving subsets, e.g., Traveling Salesman Problem.

Summary

Dynamic Programming is a powerful technique for optimization problems, leveraging overlapping subproblems and optimal substructure. By mastering DP, you can tackle a wide range of algorithmic challenges efficiently.