Dynamic Programming

Introduction

Dynamic Programming (DP) is a powerful technique for solving complex problems by breaking them down into simpler subproblem's. It is particularly useful for optimization problems where overlapping subproblem's and optimal substructure are present. In this lesson, we will explore the concepts of Dynamic Programming, its key principles, and how to implement it in Rust.

Key Points

• Dynamic Programming: A method for solving problems by breaking them into simpler overlapping subproblem's and storing their solutions.
• Optimal Substructure: A property that an optimal solution to a problem contains optimal solutions to its subproblem's.
• Overlapping Subproblem: When the same subproblem's are solved multiple times in the process of solving a larger problem.

Key Concepts

Memoization

Memoization is a top-down approach where you solve the problem by recursion and store the results of subproblem's to avoid redundant calculations.

Tabulation

Tabulation is a bottom-up approach where you solve all possible subproblem's iteratively and store their results in a table, building up the solution to the problem step by step.

Example Problems

Fibonacci Sequence

The Fibonacci sequence is a classic example to illustrate Dynamic Programming. Each number in the sequence is the sum of the two preceding ones. The problem can be solved using both memoization and tabulation.

Recursive Solution (Naive Approach)

fn fibonacci(n: u32) -> u32 {
    match n {
        0 => 0,
        1 => 1,
        _ => fibonacci(n - 1) + fibonacci(n - 2),
    }
}

fn main() {
    let n = 10;
    println!("Fibonacci of {} is {}", n, fibonacci(n));
}

Memoization Approach

use std::collections::HashMap;

fn fibonacci_memo(n: u32, memo: &mut HashMap<u32, u32>) -> u32 {
    if let Some(&result) = memo.get(&n) {
        return result;
    }

    let result = match n {
        0 => 0,
        1 => 1,
        _ => fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo),
    };

    memo.insert(n, result);
    result
}

fn main() {
    let n = 10;
    let mut memo = HashMap::new();
    println!("Fibonacci of {} is {}", n, fibonacci_memo(n, &mut memo));
}

Tabulation Approach

fn fibonacci_tab(n: u32) -> u32 {
    if n == 0 {
        return 0;
    } else if n == 1 {
        return 1;
    }

    let mut table = vec![0; (n + 1) as usize];
    table[1] = 1;

    for i in 2..=n {
        table[i as usize] = table[(i - 1) as usize] + table[(i - 2) as usize];
    }

    table[n as usize]
}

fn main() {
    let n = 10;
    println!("Fibonacci of {} is {}", n, fibonacci_tab(n));
}

Knapsack Problem

The Knapsack Problem is a classic optimization problem where you must determine the most valuable combination of items to include in a knapsack without exceeding its capacity.

Problem Definition

Given weights and values of items, and a knapsack capacity, find the maximum value that can be obtained by picking items to fit into the knapsack.

Tabulation Approach

fn knapsack(weights: &[usize], values: &[usize], capacity: usize) -> usize {
    let n = weights.len();
    let mut dp = vec![0; capacity + 1];

    for i in 0..n {
        for w in (weights[i]..=capacity).rev() {
            dp[w] = dp[w].max(dp[w - weights[i]] + values[i]);
        }
    }

    dp[capacity]
}

fn main() {
    let weights = vec![1, 2, 3];
    let values = vec![10, 15, 40];
    let capacity = 6;
    println!("Maximum value in knapsack: {}", knapsack(&weights, &values, capacity));
}

Real World Examples

• Fibonacci Sequence: Useful in problems requiring calculation of sequence values or optimization problems involving recursive calculations.
• Knapsack Problem: Common in resource allocation problems, such as budgeting or inventory management.

Conclusion

Dynamic Programming is a versatile technique for solving optimization problems by breaking them down into simpler subproblems and storing their solutions. Understanding memoization and tabulation helps you tackle complex problems more efficiently and gain deeper insights into algorithmic problem-solving.