Dynamic Programming

Dynamic Programming (DP)

Dynamic Programming (DP) is a powerful problem-solving technique used to solve complex problems by breaking them down into simpler subproblems. It is typically used for optimization problems, where the goal is to find the best solution among a set of possible solutions.

In DP, solutions to subproblems are stored (memorized) so that they are not recomputed, which greatly improves efficiency. This technique is particularly useful when the problem has overlapping subproblems and optimal substructure, which means that the solution to the overall problem can be constructed from the solutions to its subproblems.

Key Concepts in Dynamic Programming

There are two main approaches to implementing DP:

1. Top-Down Approach (Memoization):

   • In this approach, you start solving the problem from the main problem and recursively break it down into smaller subproblems.
   • Each subproblem is solved only once, and its result is stored for future use.
   • This approach uses recursion with memoization (storing results in a cache).

2. Bottom-Up Approach (Tabulation):

   • Instead of starting from the main problem, you begin by solving the smallest subproblems and build up to the solution to the overall problem.
   • This approach avoids recursion and typically uses an iterative method to fill out a table that stores solutions to subproblems.

Steps in Solving a Problem Using Dynamic Programming

1. Characterize the Structure of an Optimal Solution:

   • Identify how the solution to the problem can be broken down into smaller subproblems.
   • Express the solution as a combination of solutions to these subproblems.

2. Define the State and Recurrence Relation:

   • Define the state as a variable that represents a subproblem.
   • Derive a recurrence relation that expresses the solution of a subproblem in terms of smaller subproblems.

3. Compute the Solution (Top-Down or Bottom-Up):

   • Use either recursion with memoization (top-down) or iteration with tabulation (bottom-up) to solve the subproblems and build up to the final solution.

4. Optimize Space (Optional):

   • Some DP problems can be optimized to reduce space complexity. For example, not all previous states may be needed, so you can reduce the size of the storage.

---

Example 1: Fibonacci Numbers

The Fibonacci sequence is one of the classic examples where dynamic programming is useful. The Fibonacci number at position n is defined as:

F(n) = F(n-1) + F(n-2)  for n > 1
F(0) = 0
F(1) = 1

Naive Recursive Solution:

A simple recursive solution computes Fibonacci numbers as:

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

This recursive approach has an exponential time complexity O(2^n) because it recomputes the same values multiple times.

Optimized Solution Using Dynamic Programming:

Top-Down Approach (Memoization):

#include <iostream>
#include <vector>

std::vector<int> memo;

int fibonacci(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return memo[n];
}

int main() {
    int n = 10;
    memo.resize(n + 1, -1); // Initialize memoization array
    std::cout << "Fibonacci of " << n << " is " << fibonacci(n) << std::endl;
    return 0;
}

• Time Complexity: O(n), because each Fibonacci number is computed once and stored.
• Space Complexity: O(n) for the memoization array.

Bottom-Up Approach (Tabulation):

#include <iostream>
#include <vector>

int fibonacci(int n) {
    if (n <= 1) return n;
    std::vector<int> dp(n + 1);
    dp[0] = 0;
    dp[1] = 1;
    
    for (int i = 2; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

int main() {
    int n = 10;
    std::cout << "Fibonacci of " << n << " is " << fibonacci(n) << std::endl;
    return 0;
}

• Time Complexity: O(n), because the loop runs n times.
• Space Complexity: O(n), because the table stores Fibonacci values up to n.

Space Optimization:

In some problems, like Fibonacci, we only need the last two values to compute the next value. This allows for a space optimization to O(1).

#include <iostream>

int fibonacci(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1;
    
    for (int i = 2; i <= n; ++i) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    
    return prev1;
}

int main() {
    int n = 10;
    std::cout << "Fibonacci of " << n << " is " << fibonacci(n) << std::endl;
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1), because we only store the last two values.

---

Example 2: 0/1 Knapsack Problem

The 0/1 Knapsack Problem is another classical problem often solved using dynamic programming. In this problem, we are given a set of items, each with a weight and a value, and we need to determine the maximum value we can achieve without exceeding a weight capacity.

Problem Definition:

• We are given n items. Each item i has:
  • a value v[i]
  • a weight w[i]
• We have a knapsack with a weight capacity W.
• Our goal is to find the maximum value that can be placed in the knapsack without exceeding its capacity.

Dynamic Programming Approach:

Define dp[i][w] as the maximum value achievable with the first i items and a weight capacity w.

The recurrence relation is:

dp[i][w] = max(dp[i-1][w], dp[i-1][w - w[i]] + v[i])

• dp[i-1][w] represents the case where we don’t include item i.
• dp[i-1][w - w[i]] + v[i] represents the case where we include item i.

Solution Code (Bottom-Up):

#include <iostream>
#include <vector>

int knapsack(int W, const std::vector<int>& weights, const std::vector<int>& values, int n) {
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(W + 1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int w = 0; w <= W; ++w) {
            if (weights[i - 1] <= w) {
                dp[i][w] = std::max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][W];
}

int main() {
    int W = 50; // Knapsack capacity
    std::vector<int> weights = {10, 20, 30};
    std::vector<int> values = {60, 100, 120};
    int n = weights.size();

    std::cout << "Maximum value in knapsack = " << knapsack(W, weights, values, n) << std::endl;

    return 0;
}

Time Complexity:

• O(n * W), where n is the number of items and W is the knapsack capacity. This is because we iterate over each item and each possible weight capacity.

Space Complexity:

• O(n * W), because we store a DP table of size (n+1) x (W+1).

---

When to Use Dynamic Programming?

Dynamic Programming is effective when:

1. Optimal Substructure: The problem can be broken down into smaller subproblems that can be solved independently.
2. Overlapping Subproblems: The subproblems are not independent, meaning they share subsubproblems that can be reused.
3. Optimization Problem: You're trying to find the optimal solution (e.g., maximum profit, minimum cost).

Key Takeaways

• Memoization (top-down) uses recursion and stores intermediate results to avoid redundant calculations.
• Tabulation (bottom-up) uses iteration and fills out a table to compute the final result.
• DP is highly effective for optimization problems where subproblems overlap.