0 Interaction
0 Views
Views
0 Likes

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.

You need to be logged in to participate in this discussion.

×
×
×