Dynamic Programming - Complete Guide

Dynamic Programming is a powerful technique for solving complex problems by breaking them down into simpler subproblems. This guide covers DP fundamentals and common patterns.

What is Dynamic Programming? #

Dynamic Programming (DP) is an optimization technique that solves problems by:

  1. Breaking down into overlapping subproblems
  2. Storing results of subproblems (memoization)
  3. Reusing stored results instead of recomputing

When to Use DP? #

Use DP when a problem has:

  • Optimal substructure - Optimal solution contains optimal solutions to subproblems
  • Overlapping subproblems - Same subproblems solved multiple times

DP Approaches #

1. Top-Down (Memoization) #

Start with original problem, recursively solve subproblems, cache results.

2. Bottom-Up (Tabulation) #

Start with smallest subproblems, iteratively build up to original problem.

Classic DP Problems #

Fibonacci Numbers #

Problem: Find nth Fibonacci number.

Naive Recursion (Exponential):

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}
// Time: O(2^n), Space: O(n)

Top-Down DP (Memoization):

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

  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}
// Time: O(n), Space: O(n)

Bottom-Up DP (Tabulation):

function fib(n) {
  if (n <= 1) return n;

  const dp = [0, 1];
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
}
// Time: O(n), Space: O(n)

Space Optimized:

function fib(n) {
  if (n <= 1) return n;

  let prev = 0, curr = 1;
  for (let i = 2; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }
  return curr;
}
// Time: O(n), Space: O(1)

Climbing Stairs #

Problem: You can climb 1 or 2 stairs at a time. How many ways to reach n stairs?

function climbStairs(n) {
  if (n <= 2) return n;

  let prev = 1, curr = 2;
  for (let i = 3; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }
  return curr;
}
// Time: O(n), Space: O(1)

console.log(climbStairs(5));  // 8

Coin Change #

Problem: Minimum coins needed to make amount.

function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;

  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (i >= coin) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }

  return dp[amount] === Infinity ? -1 : dp[amount];
}
// Time: O(amount * coins.length), Space: O(amount)

console.log(coinChange([1, 2, 5], 11));  // 3 (5+5+1)

Longest Common Subsequence (LCS) #

Problem: Find length of longest common subsequence.

function longestCommonSubsequence(text1, text2) {
  const m = text1.length, n = text2.length;
  const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  return dp[m][n];
}
// Time: O(m*n), Space: O(m*n)

console.log(longestCommonSubsequence("abcde", "ace"));  // 3

Longest Increasing Subsequence #

Problem: Find length of longest increasing subsequence.

function lengthOfLIS(nums) {
  const n = nums.length;
  const dp = new Array(n).fill(1);

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

  return Math.max(...dp);
}
// Time: O(n^2), Space: O(n)

console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]));  // 4

0/1 Knapsack #

Problem: Maximum value with weight limit.

function knapsack(weights, values, capacity) {
  const n = weights.length;
  const dp = Array(n + 1).fill(0).map(() => Array(capacity + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      if (weights[i - 1] <= w) {
        dp[i][w] = Math.max(
          dp[i - 1][w],  // Don't take
          dp[i - 1][w - weights[i - 1]] + values[i - 1]  // Take
        );
      } else {
        dp[i][w] = dp[i - 1][w];
      }
    }
  }

  return dp[n][capacity];
}
// Time: O(n*capacity), Space: O(n*capacity)

const weights = [1, 3, 4, 5];
const values = [1, 4, 5, 7];
console.log(knapsack(weights, values, 7));  // 9

Edit Distance #

Problem: Minimum operations to convert string1 to string2.

function editDistance(word1, word2) {
  const m = word1.length, n = word2.length;
  const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));

  // Initialize base cases
  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j],      // Delete
          dp[i][j - 1],      // Insert
          dp[i - 1][j - 1]   // Replace
        );
      }
    }
  }

  return dp[m][n];
}
// Time: O(m*n), Space: O(m*n)

console.log(editDistance("horse", "ros"));  // 3

Maximum Subarray (Kadane’s Algorithm) #

Problem: Find maximum sum subarray.

function maxSubArray(nums) {
  let maxSum = nums[0];
  let currentSum = nums[0];

  for (let i = 1; i < nums.length; i++) {
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    maxSum = Math.max(maxSum, currentSum);
  }

  return maxSum;
}
// Time: O(n), Space: O(1)

console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]));  // 6

House Robber #

Problem: Maximize money robbed without robbing adjacent houses.

function rob(nums) {
  if (nums.length === 0) return 0;
  if (nums.length === 1) return nums[0];

  let prev = 0, curr = 0;

  for (const num of nums) {
    [prev, curr] = [curr, Math.max(curr, prev + num)];
  }

  return curr;
}
// Time: O(n), Space: O(1)

console.log(rob([2, 7, 9, 3, 1]));  // 12 (2+9+1)

Unique Paths #

Problem: Number of paths from top-left to bottom-right.

function uniquePaths(m, n) {
  const dp = Array(m).fill(0).map(() => Array(n).fill(1));

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }

  return dp[m - 1][n - 1];
}
// Time: O(m*n), Space: O(m*n)

console.log(uniquePaths(3, 7));  // 28

Space Optimized:

function uniquePaths(m, n) {
  const dp = new Array(n).fill(1);

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[j] += dp[j - 1];
    }
  }

  return dp[n - 1];
}
// Time: O(m*n), Space: O(n)

Partition Equal Subset Sum #

Problem: Can partition array into two equal sum subsets?

function canPartition(nums) {
  const total = nums.reduce((sum, num) => sum + num, 0);

  if (total % 2 !== 0) return false;

  const target = total / 2;
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;

  for (const num of nums) {
    for (let j = target; j >= num; j--) {
      dp[j] = dp[j] || dp[j - num];
    }
  }

  return dp[target];
}
// Time: O(n*sum), Space: O(sum)

console.log(canPartition([1, 5, 11, 5]));  // true

Longest Palindromic Substring #

Problem: Find longest palindromic substring.

function longestPalindrome(s) {
  const n = s.length;
  const dp = Array(n).fill(false).map(() => Array(n).fill(false));

  let start = 0, maxLen = 1;

  // All single characters are palindromes
  for (let i = 0; i < n; i++) {
    dp[i][i] = true;
  }

  // Check for length 2
  for (let i = 0; i < n - 1; i++) {
    if (s[i] === s[i + 1]) {
      dp[i][i + 1] = true;
      start = i;
      maxLen = 2;
    }
  }

  // Check for lengths > 2
  for (let len = 3; len <= n; len++) {
    for (let i = 0; i < n - len + 1; i++) {
      const j = i + len - 1;

      if (s[i] === s[j] && dp[i + 1][j - 1]) {
        dp[i][j] = true;
        start = i;
        maxLen = len;
      }
    }
  }

  return s.substring(start, start + maxLen);
}
// Time: O(n^2), Space: O(n^2)

console.log(longestPalindrome("babad"));  // "bab" or "aba"

Word Break #

Problem: Can string be segmented into dictionary words?

function wordBreak(s, wordDict) {
  const n = s.length;
  const dp = new Array(n + 1).fill(false);
  dp[0] = true;

  const wordSet = new Set(wordDict);

  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && wordSet.has(s.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }

  return dp[n];
}
// Time: O(n^2), Space: O(n)

console.log(wordBreak("leetcode", ["leet", "code"]));  // true

DP Patterns #

Linear DP #

  • Fibonacci, Climbing Stairs, House Robber
  • 1D array, decision at each step

Grid DP #

  • Unique Paths, Minimum Path Sum
  • 2D array, move through grid

Subsequence DP #

  • LCS, LIS, Edit Distance
  • Compare elements, build solution

Knapsack DP #

  • 0/1 Knapsack, Partition Equal Subset
  • Include/exclude decisions

Interval DP #

  • Longest Palindromic Substring
  • Solve for all intervals

DP Problem-Solving Steps #

  1. Identify if problem has optimal substructure and overlapping subproblems
  2. Define state (what does dp[i] represent?)
  3. Find recurrence relation (how to compute dp[i]?)
  4. Initialize base cases
  5. Determine iteration order
  6. Return final answer

Time and Space Optimization #

Space Optimization #

Often can reduce from 2D to 1D:

// 2D DP
const dp = Array(m).fill(0).map(() => Array(n).fill(0));

// 1D DP (space optimized)
const dp = new Array(n).fill(0);

When to Use Each Approach #

Top-Down (Memoization):

  • Easier to write (recursive)
  • Only computes needed subproblems
  • Stack space overhead

Bottom-Up (Tabulation):

  • More efficient (no recursion)
  • Computes all subproblems
  • Easier to optimize space

Common Mistakes #

  1. Wrong base cases - Always double-check
  2. Index errors - Off-by-one mistakes
  3. Wrong recurrence relation - Test with examples
  4. Not considering all options - Include/exclude, buy/sell, etc.
  5. Forgetting to initialize - Set base cases correctly

Practice Tips #

  1. Start with brute force - Understand the problem
  2. Identify overlapping subproblems - Draw recursion tree
  3. Add memoization - Cache results
  4. Convert to bottom-up - If needed
  5. Optimize space - Reduce dimensions
  6. Test with examples - Verify solution

Dynamic programming is essential for coding interviews. Master these patterns and you can solve most DP problems efficiently.

Previous Greedy Algorithms - Complete Guide Graph Traversal Algorithms - Complete Guide Next