Dynamic Programming: Mastering Optimization

Learn Dynamic Programming (DP) techniques to solve complex problems efficiently. Covers memoization, tabulation, and advanced patterns with real-world applications.

DP Usage in Industry (2023)

Optimization (35%)

Finance (25%)

Game AI (20%)

Bioinformatics (20%)

1. DP Fundamentals

Core Principles:

Optimal Substructure: Solution depends on optimal subproblems
Overlapping Subproblems: Recomputations can be avoided
Memoization: Top-down cache (recursive)
Tabulation: Bottom-up table (iterative)

Time Complexities:

Problem	Brute Force	DP Solution
Fibonacci	O(2ⁿ)	O(n)
0/1 Knapsack	O(2ⁿ)	O(nW)
Longest Common Subsequence	O(2ⁿ)	O(mn)
Matrix Chain Multiplication	O(n!)	O(n³)

Fibonacci Example:

Memoization (Top-Down)


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

Tabulation (Bottom-Up)


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

2. Classic DP Problems

0/1 Knapsack


function knapsack(values, weights, W) {
  const n = values.length;
  const dp = Array(n+1).fill().map(() => Array(W+1).fill(0));
  
  for (let i = 1; i <= n; i++) {
    for (let w = 1; w <= W; w++) {
      if (weights[i-1] <= w) {
        dp[i][w] = Math.max(
          values[i-1] + dp[i-1][w-weights[i-1]], 
          dp[i-1][w]
        );
      } else {
        dp[i][w] = dp[i-1][w];
      }
    }
  }
  return dp[n][W];
}

Use Case: Resource allocation

Longest Common Subsequence


function LCS(text1, text2) {
  const m = text1.length, n = text2.length;
  const dp = Array(m+1).fill().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];
}

Use Case: DNA sequence alignment

3. Advanced DP Patterns

DP on Strings

Edit Distance


function minDistance(word1, word2) {
  const m = word1.length, n = word2.length;
  const dp = Array(m+1).fill().map(() => Array(n+1).fill(0));
  
  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];
}

Longest Palindromic Subsequence


function longestPalindromeSubseq(s) {
  const n = s.length;
  const dp = Array(n).fill().map(() => Array(n).fill(0));
  
  for (let i = n-1; i >= 0; i--) {
    dp[i][i] = 1;
    for (let j = i+1; j < n; j++) {
      if (s[i] === s[j]) {
        dp[i][j] = 2 + dp[i+1][j-1];
      } else {
        dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
      }
    }
  }
  return dp[0][n-1];
}

State Machine DP


// Best Time to Buy/Sell Stock with Cooldown
function maxProfit(prices) {
  let held = -Infinity, sold = 0, reset = 0;
  
  for (const price of prices) {
    const prevHeld = held;
    held = Math.max(held, reset - price);
    reset = sold;
    sold = prevHeld + price;
  }
  
  return Math.max(sold, reset);
}

DP Problem Patterns

Pattern	Example Problems	Approach
0/1 Knapsack	Subset Sum, Partition Equal Subset Sum	DP[i][w] = max(include, exclude)
Unbounded Knapsack	Coin Change, Rod Cutting	DP[i] = min/max(DP[i], DP[i-coin]+1)
LCS Variants	Edit Distance, Longest Palindromic Substring	DP[i][j] based on character match
State Machine	Stock Trading, House Robber	Track multiple states (buy/sell/cooldown)

4. Real-World Applications

Financial Optimization

Portfolio Management: Knapsack for asset allocation

function optimizePortfolio(assets, maxRisk) {
  // assets = [{return, risk}]
  const dp = Array(assets.length+1)
    .fill().map(() => Array(maxRisk+1).fill(0));
  // DP solution similar to knapsack
}

Natural Language Processing

Spell Correction: Edit distance for suggestions

function suggestCorrection(word, dictionary) {
  return dictionary
    .map(w => ({ word: w, dist: editDistance(word, w) }))
    .sort((a, b) => a.dist - b.dist);
}

Game Development

Pathfinding: DP for optimal moves in strategy games

function optimalMoves(gameState) {
  const dp = {}; // Memoize game states
  // Recursive DP with alpha-beta pruning
}

DP Problem-Solving Checklist

✓ Identify overlapping subproblems

✓ Define state transition clearly

✓ Choose memoization (top-down) or tabulation (bottom-up)

✓ Optimize space if possible (e.g., use 1D array)

✓ Handle base cases carefully

Expert Tip: For DP problems, always start with a recursive brute force solution, then add memoization. Finally, convert to tabulation for optimal performance. Drawing the state transition diagram helps visualize the solution.

0 Interaction

0 Views

0 Likes