Dynamic Programming Explained

January 22, 2025 | Algorithms

Dynamic Programming (DP) is an optimization technique used to solve problems by breaking them down into smaller overlapping subproblems and storing their results to avoid redundant computations.

Key Concepts

1. Optimal Substructure

A problem has an optimal substructure if its solution can be composed of the optimal solutions of its subproblems.

2. Overlapping Subproblems

A problem has overlapping subproblems if the same smaller problems are solved multiple times.

Approaches to Dynamic Programming

Memoization (Top-Down Approach)

Memoization involves solving the problem recursively and storing results to avoid recomputation.

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

console.log(fibonacci(10)); // Expected Output: 55

Tabulation (Bottom-Up Approach)

Tabulation uses an iterative approach to build the solution from the ground up.

function fibonacciTab(n) {
  if (n <= 1) return n;
  let dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}

console.log(fibonacciTab(10)); // Expected Output: 55

Common Problems Solved with DP

• Fibonacci Sequence
• Knapsack Problem
• Longest Common Subsequence
• Coin Change Problem

When to Use Dynamic Programming

Use DP when:

1. The problem can be broken into smaller subproblems.
2. The subproblems overlap (same computation appears multiple times).