Implementing Dynamic Programming Solutions

1. Building DP Foundation

Concept	Description	Key Characteristics
Overlapping Subproblems	Problem can be broken into smaller subproblems that are solved multiple times	Optimal substructure and memoization needed
Optimal Substructure	Optimal solution contains optimal solutions to subproblems	Can be solved with recursion or iteration
Memoization	Storing results of expensive function calls to avoid recomputation	Top-down approach, uses cache or hash map
Tabulation	Building solution from bottom-up using a table	Bottom-up approach, avoids recursion stack

Example: Fibonacci Sequence

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

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

DP Core Principles

Identify overlapping subproblems in recursive structure
Choose between memoization (top-down) or tabulation (bottom-up)
Build recurrence relation from problem decomposition
Optimize space complexity by tracking only necessary states

2. Solving Climbing Stairs

The Climbing Stairs problem is a classic dynamic programming challenge where you're tasked with finding the number of distinct ways to reach the top of a staircase with n steps, given that you can climb either 1 or 2 steps at a time.

Approach	Description	Time Complexity	Space Complexity
Recursive	Naive recursive solution without memoization. Leads to exponential time.	O(2^n)	O(n)
Memoization	Recursive with memoization to store computed values.	O(n)	O(n)
Tabulation (Bottom-Up)	Build up solution iteratively using a DP array.	O(n)	O(n)
Space-Optimized	Use only two variables to track previous states, reducing space to O(1).	O(n)	O(1)

Example: Space-Optimized Solution

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

    let prev2 = 1; // ways to reach step 1
    let prev1 = 2; // ways to reach step 2

    for (let i = 3; i <= n; i++) {
        let current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
}

// Example usage:
console.log(climbStairs(5)); // Output: 8

Note: This problem is mathematically equivalent to computing the (n+1)-th Fibonacci number.

3. Solving Maximum Subarray

Approach	Description	Time Complexity	Space Complexity
Kadane's Algorithm	Dynamic programming approach that tracks maximum sum ending at each position	`O(n)`	`O(1)`
Brute Force	Check all possible subarrays and compute their sums	`O(n^2)`	`O(1)`
Divide and Conquer	Recursively divide array into halves and find max subarray in left, right, or crossing	`O(n log n)`	`O(log n)`

Example: Kadane's Algorithm Implementation

function maxSubArray(nums) {
  let maxSoFar = nums[0];
  let maxEndingHere = nums[0];

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

  return maxSoFar;
}

// Example usage:
const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log(maxSubArray(nums)); // Output: 6 (subarray [4, -1, 2, 1])

Example: Brute Force Approach

function maxSubArrayBrute(nums) {
  let maxSum = -Infinity;

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

  return maxSum;
}

// Example usage:
const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
console.log(maxSubArrayBrute(nums)); // Output: 6

Note: Kadane's algorithm is optimal for this problem with linear time complexity and constant space.

4. Solving House Robber

The House Robber problem is a classic dynamic programming challenge where you must determine the maximum amount of money that can be robbed from houses arranged in a line, given that adjacent houses cannot be robbed.

Property	Description	Values
Input	Array of integers representing money in each house	`[1, 2, 3, 1]`
Constraint	Cannot rob adjacent houses	Adjacent indices cannot be selected
Output	Maximum money that can be robbed	`4`

Example: House Robber Problem

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

  let prev2 = houses[0];
  let prev1 = Math.max(houses[0], houses[1]);

  for (let i = 2; i < houses.length; i++) {
    let current = Math.max(prev1, prev2 + houses[i]);
    prev2 = prev1;
    prev1 = current;
  }

  return prev1;
}

// Example usage:
const houses = [1, 2, 3, 1];
console.log(rob(houses)); // Output: 4

Note: The solution uses a space-optimized dynamic programming approach where we only keep track of the last two computed values to reduce space complexity to O(1).

5. Solving 0/1 Knapsack

Property	Description	Values
weights	Array of item weights	`[2, 1, 3, 2]`
values	Array of item values	`[3, 2, 4, 2]`
capacity	Maximum weight capacity of knapsack	`4`

Example: 0/1 Knapsack Implementation

function knapsack(weights, values, capacity) {
  const n = weights.length;
  const dp = Array(n + 1).fill().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],
          dp[i - 1][w - weights[i - 1]] + values[i - 1]
        );
      } else {
        dp[i][w] = dp[i - 1][w];
      }
    }
  }

  return dp[n][capacity];
}

const weights = [2, 1, 3, 2];
const values = [3, 2, 4, 2];
const capacity = 4;
console.log(knapsack(weights, values, capacity)); // Output: 7

Note: The 0/1 Knapsack problem involves selecting items with maximum value without exceeding the weight capacity. Each item can only be taken once.

6. Solving Unbounded Knapsack

The unbounded knapsack problem allows items to be used multiple times, unlike the 0/1 knapsack where each item can only be used once. It's a classic dynamic programming problem.

Property	Description	Notes
Items	List of items with weight and value	Each item can be used unlimited times
Capacity	Maximum weight the knapsack can hold	Fixed integer value
Goal	Maximize value within capacity	Same as 0/1 knapsack, but with repetition

Example: Unbounded Knapsack Solution

function unboundedKnapsack(weights, values, capacity) {
  const dp = Array(capacity + 1).fill(0);
  
  for (let i = 1; i <= capacity; i++) {
    for (let j = 0; j < weights.length; j++) {
      if (weights[j] <= i) {
        dp[i] = Math.max(dp[i], dp[i - weights[j]] + values[j]);
      }
    }
  }
  
  return dp[capacity];
}

// Example usage:
const weights = [2, 3, 4, 5];
const values = [3, 4, 5, 6];
const capacity = 8;
console.log(unboundedKnapsack(weights, values, capacity)); // Output: 12

Note: Unlike 0/1 knapsack, this solution uses a 1D array and iterates through weights in the inner loop to allow reuse of items.

7. Solving Coin Change

Property	Description	Values
coin denominations	Array of available coin values	`[1, 3, 4]`
target amount	Amount to make change for	`6`
minimum coins needed	Minimum number of coins to make target amount	`2`

Example: Coin Change Solution

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 (coin <= i) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }

  return dp[amount] === Infinity ? -1 : dp[amount];
}

// Example usage:
const coins = [1, 3, 4];
const amount = 6;
console.log(coinChange(coins, amount)); // Output: 2

Note: The solution uses dynamic programming with a 1D array where dp[i] represents the minimum coins needed to make amount i.

8. Solving Partition Equal Subset Sum

The Partition Equal Subset Sum problem asks whether a given array of positive integers can be partitioned into two subsets with equal sums.

Problem	Description	Solution Approach
Input	Array of positive integers	Dynamic Programming (0/1 Knapsack variant)
Output	Boolean indicating if partition is possible

This problem is a variation of the classic 0/1 Knapsack problem. If the total sum of the array is odd, it's impossible to partition into two equal subsets.

Example: Partition Equal Subset Sum

function canPartition(nums) {
    const totalSum = nums.reduce((sum, num) => sum + num, 0);
    if (totalSum % 2 !== 0) return false;

    const target = totalSum / 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];
}

// Example usage:
console.log(canPartition([1, 5, 11, 5])); // true
console.log(canPartition([1, 2, 3, 5]));  // false

Note: The solution uses a 1D DP array to optimize space complexity. It iterates through numbers and updates the possible subset sums up to half of the total sum.

9. Finding Longest Common Subsequence

Property	Description	Example
Problem	Finds the longest subsequence common to two sequences	`str1 = "ABCDGH"`, `str2 = "AEDFHR"`
Approach	Dynamic Programming with 2D table	Build a matrix where `dp[i][j]` represents LCS length of `str1[0..i-1]` and `str2[0..j-1]`
Time Complexity	O(m × n)	Where m and n are lengths of input strings
Space Complexity	O(m × n)	For the DP table

Example: LCS Implementation

function longestCommonSubsequence(str1, str2) {
  const m = str1.length;
  const n = str2.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 (str1[i - 1] === str2[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];
}

// Example usage
const str1 = "ABCDGH";
const str2 = "AEDFHR";
console.log(longestCommonSubsequence(str1, str2)); // Output: 3 ("ADH")

Note: The LCS can be reconstructed by backtracking through the DP table.

10. Finding Longest Increasing Subsequence

Property	Description	Time Complexity	Space Complexity
LIS Length	Length of the longest increasing subsequence	`O(n^2)`	`O(n)`
LIS Array	Array storing the actual longest increasing subsequence	`O(n^2)`	`O(n)`

Example: Finding LIS using Dynamic Programming

function longestIncreasingSubsequence(arr) {
  const n = arr.length;
  if (n === 0) return [];

  const dp = new Array(n).fill(1);
  const parent = new Array(n).fill(-1);

  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
        dp[i] = dp[j] + 1;
        parent[i] = j;
      }
    }
  }

  let maxLength = 0;
  let maxIndex = 0;
  for (let i = 0; i < n; i++) {
    if (dp[i] > maxLength) {
      maxLength = dp[i];
      maxIndex = i;
    }
  }

  const lis = [];
  let current = maxIndex;
  while (current !== -1) {
    lis.unshift(arr[current]);
    current = parent[current];
  }

  return lis;
}

const arr = [10, 9, 2, 5, 3, 7, 101, 18];
console.log(longestIncreasingSubsequence(arr)); // [2, 3, 7, 18]

Example: Optimized LIS using Binary Search

function lisBinarySearch(arr) {
  if (arr.length === 0) return [];

  const tails = [];
  const predecessors = new Array(arr.length).fill(-1);
  const indices = new Array(arr.length).fill(0);

  for (let i = 0; i < arr.length; i++) {
    let left = 0;
    let right = tails.length;

    while (left < right) {
      const mid = Math.floor((left + right) / 2);
      if (tails[mid] < arr[i]) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }

    if (left === tails.length) {
      tails.push(arr[i]);
    } else {
      tails[left] = arr[i];
    }

    if (left !== 0) {
      predecessors[i] = indices[left - 1];
    }

    indices[left] = i;
  }

  const result = [];
  let current = indices[tails.length - 1];
  while (current !== -1) {
    result.unshift(arr[current]);
    current = predecessors[current];
  }

  return result;
}

const arr2 = [10, 9, 2, 5, 3, 7, 101, 18];
console.log(lisBinarySearch(arr2)); // [2, 3, 7, 18]

Note: The optimized version using binary search reduces the time complexity to O(n log n).

11. Solving Edit Distance

Edit Distance (also known as Levenshtein Distance) is a classic dynamic programming problem that measures the minimum number of single-character edits (insertions, deletions, or substitutions) required to change one string into another.

Operation	Cost	Description
Insert	`1`	Insert a character at any position
Delete	`1`	Delete a character at any position
Substitute	`1`	Replace a character with another character

Example: Calculating Edit Distance

function editDistance(str1, str2) {
  const m = str1.length;
  const n = str2.length;

  // Create a 2D DP table
  const dp = Array(m + 1)
    .fill()
    .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;

  // Fill the DP table
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (str1[i - 1] === str2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j],     // Deletion
          dp[i][j - 1],     // Insertion
          dp[i - 1][j - 1]  // Substitution
        );
      }
    }
  }

  return dp[m][n];
}

// Example usage:
console.log(editDistance("kitten", "sitting")); // Output: 3

Algorithm Summary

State: dp[i][j] represents the edit distance between str1[0..i-1] and str2[0..j-1].
Transition: If characters match, take the diagonal value; otherwise, take the minimum of three operations plus 1.
Base Case: dp[i][0] = i and dp[0][j] = j.
Time Complexity: O(m * n)
Space Complexity: O(m * n)

12. Solving Word Break

Property	Description	Example
Problem	Given a string and a dictionary of words, determine if the string can be segmented into a sequence of dictionary words.	`"leetcode"` with dictionary `["leet", "code"]`
Approach	Dynamic Programming using a boolean array to track if substring up to index i can be segmented.	DP array `dp[i]` represents whether substring `s[0..i-1]` can be segmented.

Example: Word Break Implementation

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

    for (let i = 1; i <= s.length; i++) {
        for (const word of wordDict) {
            if (i >= word.length && s.substring(i - word.length, i) === word) {
                dp[i] = dp[i] || dp[i - word.length];
            }
        }
    }

    return dp[s.length];
}

// Example usage:
const s = "leetcode";
const wordDict = ["leet", "code"];
console.log(wordBreak(s, wordDict)); // true

Note: The solution uses a bottom-up DP approach where dp[i] indicates if the substring s[0..i-1] can be segmented into dictionary words.

13. Solving Palindrome Partitioning II

The Palindrome Partitioning II problem involves partitioning a string such that every substring in the partition is a palindrome, and minimizing the number of cuts needed.

Property	Description	Value
Input	String to partition	`"aab"`
Output	Minimum number of cuts to make all substrings palindromes	`1`

Example: Palindrome Partitioning II

function minCut(s) {
    const n = s.length;
    const isPalindrome = Array(n).fill().map(() => Array(n).fill(false));
    const cuts = Array(n).fill(0);

    // Precompute palindromes
    for (let i = 0; i < n; i++) {
        isPalindrome[i][i] = true;
    }

    for (let length = 2; length <= n; length++) {
        for (let i = 0; i < n - length + 1; i++) {
            const j = i + length - 1;
            if (s[i] === s[j]) {
                if (length === 2 || isPalindrome[i + 1][j - 1]) {
                    isPalindrome[i][j] = true;
                }
            }
        }
    }

    // Dynamic Programming to find minimum cuts
    for (let i = 0; i < n; i++) {
        if (isPalindrome[0][i]) {
            cuts[i] = 0;
        } else {
            cuts[i] = i; // Worst case: cut at every position
            for (let j = 1; j <= i; j++) {
                if (isPalindrome[j][i]) {
                    cuts[i] = Math.min(cuts[i], cuts[j - 1] + 1);
                }
            }
        }
    }

    return cuts[n - 1];
}

// Example usage:
console.log(minCut("aab")); // Output: 1

Note: The solution uses a two-step dynamic programming approach: first precompute all palindromic substrings, then compute the minimum cuts needed.

14. Solving Egg Drop Problem

Parameter	Description	Values
n	Number of floors	Positive integer
k	Number of eggs	Positive integer

Example: Egg Drop Problem with 2 Eggs and 10 Floors

function eggDrop(n, k) {
    // Create a 2D DP table
    const dp = Array(k + 1)
        .fill()
        .map(() => Array(n + 1).fill(0));

    // Base cases
    for (let i = 1; i <= n; i++) {
        dp[1][i] = i; // With 1 egg, must test each floor
    }

    for (let i = 1; i <= k; i++) {
        dp[i][0] = 0; // With 0 floors, 0 moves needed
        dp[i][1] = 1; // With 1 floor, 1 move needed
    }

    // Fill the DP table
    for (let i = 2; i <= k; i++) {
        for (let j = 2; j <= n; j++) {
            dp[i][j] = Number.MAX_SAFE_INTEGER;
            for (let x = 1; x <= j; x++) {
                const res = 1 + Math.max(dp[i - 1][x - 1], dp[i][j - x]);
                dp[i][j] = Math.min(dp[i][j], res);
            }
        }
    }

    return dp[k][n];
}

// Example usage
console.log(eggDrop(10, 2)); // Output: 4

Note: The solution uses dynamic programming to minimize the number of moves required to determine the critical floor with certainty.

15. Solving Matrix Chain Multiplication

Matrix Chain Multiplication (MCM) is a classic dynamic programming problem that aims to find the most efficient way to multiply a sequence of matrices. The goal is to minimize the number of scalar multiplications required.

Parameter	Description	Values
p	Array of matrix dimensions, where `p[i]` is the number of rows of matrix `i` and `p[i+1]` is the number of columns of matrix `i`	`[p0, p1, ..., pn]`
m[i][j]	Minimum number of scalar multiplications needed to compute the product of matrices from `i` to `j`	Integer
s[i][j]	Index of the optimal split point for matrices from `i` to `j`	Integer

Example: Matrix Chain Multiplication

function matrixChainOrder(p) {
    const n = p.length - 1;
    const m = Array(n).fill().map(() => Array(n).fill(0));
    const s = Array(n).fill().map(() => Array(n).fill(0));

    for (let len = 2; len <= n; len++) {
        for (let i = 1; i <= n - len + 1; i++) {
            const j = i + len - 1;
            m[i][j] = Infinity;
            for (let k = i; k < j; k++) {
                const q = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j];
                if (q < m[i][j]) {
                    m[i][j] = q;
                    s[i][j] = k;
                }
            }
        }
    }

    return { m, s };
}

// Example usage:
const dimensions = [10, 20, 30, 40, 30];
const result = matrixChainOrder(dimensions);
console.log(result.m[1][4]); // Minimum scalar multiplications

Note: The optimal parenthesization can be reconstructed using the s matrix to build the expression tree.

Key Points

MCM uses dynamic programming to find the optimal order of matrix multiplication.
Time complexity is O(n^3), space complexity is O(n^2).
It involves computing a cost matrix m and split point matrix s.