⛓️ Dynamic Programming Lecture with Alvin

Overview

Dynamic programming is often seen as a difficult topic, but can be intuitive with a gradual approach.
Essential for data structure and algorithm interviews.
Course covers problems like: Fibonacci sequence, grid traversal, coin change, substring construction.

Course Format

Visualization is key: drawings, whiteboard, animations.
Heavy lifting involves designing the algorithm.
Code implementation is secondary to algorithm design.

Structure

Part 1: Memoization
Part 2: Tabulation

Prerequisites

Basic understanding of recursion.
Familiarity with complexity analysis (Big O notation).

Example Problems

Fibonacci Sequence with Memoization

Problem Statement:

Write fib(n) to return the n-th Fibonacci number.
Sequence: 1, 1, 2, 3, 5, 8, 13, ...

Recursive Implementation

function fib(n) {
  if (n <= 2) return 1;
  return fib(n - 1) + fib(n - 2);
}

Slow for large n due to redundant calculations.

Memoization Strategy

Use a JavaScript object to store results of function calls.
Key: function argument, Value: return value.

function fib(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 2) return 1;
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}

Grid Traveler Problem with Memoization

Problem Statement:

Calculate number of ways to travel from top-left to bottom-right on an m x n grid, moving only right or down.

Recursive Implementation

function gridTraveler(m, n) {
  if (m == 1 && n == 1) return 1;
  if (m == 0 || n == 0) return 0;
  return gridTraveler(m - 1, n) + gridTraveler(m, n - 1);
}

Memoization Strategy

function gridTraveler(m, n, memo = {}) {
  const key = m + ',' + n;
  if (key in memo) return memo[key];
  if (m == 1 && n == 1) return 1;
  if (m == 0 || n == 0) return 0;
  memo[key] = gridTraveler(m - 1, n, memo) + gridTraveler(m, n - 1, memo);
  return memo[key];
}

CanSum Problem with Memoization

Problem Statement:

Determine if it is possible to generate a target sum using numbers from an array (reuse allowed).

Recursive Implementation

function canSum(targetSum, numbers) {
  if (targetSum == 0) return true;
  if (targetSum < 0) return false;
  for (let num of numbers) {
    const remainder = targetSum - num;
    if (canSum(remainder, numbers) === true) {
      return true;
    }
  }
  return false;
}

Memoization Strategy

function canSum(targetSum, numbers, memo = {}) {
  if (targetSum in memo) return memo[targetSum];
  if (targetSum == 0) return true;
  if (targetSum < 0) return false;
  for (let num of numbers) {
    const remainder = targetSum - num;
    if (canSum(remainder, numbers, memo) === true) {
      memo[targetSum] = true;
      return true;
    }
  }
  memo[targetSum] = false;
  return false;
}

Memoization Recipe

Visualize: Draw the problem as a tree, nodes are function calls, edges are recursive steps.
Base Case: Leaves of the tree, simplified problem solutions.
Recursive Case: Translate the tree structure into recursive code.
Memoization: Implement a cache to store results of function calls.
- Add memo object, use function arguments as keys.
- Check cache before computing.
- Store result in cache before returning.

Dynamic Programming Problem Types

Decision Problem (CanSum): Yes or No answer.
Combinatorial Problem (HowSum): Return combinations.
Optimization Problem (BestSum): Return the best combination.

Summary

Dynamic programming simplifies complex problems by breaking them down into simpler subproblems and storing the results of these subproblems to avoid redundant calculations.
Memoization and tabulation are key strategies in dynamic programming.
Visualizing the problem and understanding its structure is crucial before writing the code.
Practicing both memoization and tabulation approaches strengthens problem-solving skills.

End of Lecture Summary