Skip to main content

Dynamic Programming

Dynamic Programming (DP) is a technique used for solving complex problems by breaking them down into simpler overlapping subproblems. It involves storing the results of these subproblems to avoid redundant computations. There are two main approaches to implementing DP: Top-Down and Bottom-Up.

Top-Down Approach (Memoization)​

In the Top-Down approach, also known as Memoization, the problem is solved by recursively breaking it down into subproblems. Each subproblem's result is stored in a data structure (like an array or hash map) to avoid redundant calculations.

Steps​

  1. Recursive Definition:

    • Define the problem recursively in terms of smaller subproblems.

  2. Memoization:

    • Use a data structure (memoization table) to store the results of subproblems.

  3. Recursion:

    • Solve the problem by making recursive calls and using the memoized results.

Example: Fibonacci Numbers​

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

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

Bottom-Up Approach (Tabulation)​

In the Bottom-Up approach, also known as Tabulation, the problem is solved by iteratively building up solutions to subproblems starting from the smallest subproblems. Results are stored in a table to build up the final solution.

Steps​

Initialization​

  1. Initialize a table to store solutions to subproblems. Iteration:

  2. Solve smaller subproblems iteratively and store their results in the table. Build Solution:

  3. Use the results of smaller subproblems to build up the solution to the larger problem. Example: Fibonacci Numbers

function fibonacci(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];
}

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

Dynamic Programming Problems

Fibonacci Style​

Matrix​

On Strings​

Longest Increasing Subsequence​

Longest Common Subsequence​

Best Time to Buy & Sell Stock / State Machine​

On Trees​

Knapsack​

General 1D​

2D Grid DP Problems​

3D Grid DP Problems​

Dynamic Programming: Knapsack Problems

0/1 Knapsack Problem​

Constraint​

You can either include or exclude an item, i.e., you can take at most one of each item.

Objective​

Maximize the total value of items chosen such that their combined weight is less than or equal to a given capacity.

Decision​

For each item, you have a binary choice (0 or 1)—either take it or leave it.

Approach​

Dynamic programming is often used, where each subproblem considers whether to include or exclude a particular item.

Recurrence Relation​

The recurrence relation is typically:

dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])

Where:

  • i is the item index,
  • w is the current weight capacity.
const knapsack01 = (W, items) => {
  const n = items.length;
  const dp = Array(W + 1).fill(0); // DP table to store the max profit for each weight limit

  // Iterate over each item
  for (let i = 0; i < n; i++) {
    const { weight, profit } = items[i];

    // Traverse DP table backwards to avoid overwriting values in the same round
    for (let w = W; w >= weight; w--) {
      dp[w] = Math.max(dp[w], dp[w - weight] + profit);
    }
  }

  return dp[W]; // Max profit for capacity W
}

// Example usage:
const items01 = [
  { weight: 1, profit: 60 },
  { weight: 2, profit: 100 },
  { weight: 3, profit: 120 }
];
const W01 = 5;
console.log(knapsack01(W01, items01)); // Output: 220
/* 
TC : O(N*W)
SC : O(W)
*/

0/1 Knapsack Fractional Weight​

const fractionalKnapsack = (W, items) => {
    // Sort items by profit-to-weight ratio in descending order
    items.sort((a, b) => (b.profit / b.weight) - (a.profit / a.weight));

    let totalProfit = 0;
    for (let i = 0; i < items.length && W > 0; i++) {
        if (W >= items[i].weight) {
            // Take the full item
            totalProfit += items[i].profit;
            W -= items[i].weight;
        } else {
            // Take a fraction of the item
            totalProfit += (W / items[i].weight) * items[i].profit;
            break;
        }
    }
    return totalProfit;
}

// Example usage:
const items = [
    { weight: 4, profit: 12 },
    { weight: 2, profit: 10 },
    { weight: 1, profit: 4 }
];
const W = 5;
console.log(fractionalKnapsack(W, items)); // Output: 16
/* 
TC : O(N*logN)
SC : O(1)
*/

Unbounded Knapsack Problem​

Constraint​

There is no limit on how many times you can take each item, i.e., you can take an unlimited number of each item.

Objective​

Similar to the 0/1 problem—maximize the total value while adhering to a weight constraint.

Decision​

For each item, you can include it any number of times, or not include it at all.

Approach​

Dynamic programming is also used, but the recurrence allows taking an item multiple times.

Recurrence Relation​

The recurrence relation is:

dp[w] = max(dp[w], dp[w - weight[i]] + value[i])

Where w is the current weight capacity. Notice that the i-th item can be considered multiple times.

Key Differences​

Item Usage​

  • 0/1 Knapsack: Each item can only be selected once.
  • Unbounded Knapsack: Items can be selected multiple times.

State Representation​

  • 0/1 Knapsack: Typically uses a 2D array dp[i][w], where i is the index of the item, and w is the current weight.
  • Unbounded Knapsack: Uses a 1D array dp[w] since each item can be used more than once, eliminating the need for the second dimension.

Complexity​

  • 0/1 Knapsack: Time complexity is O(nW), where n is the number of items and W is the knapsack capacity.
  • Unbounded Knapsack: Time complexity is also O(nW), but the recursive calls allow for the same item to be picked multiple times.
const unboundedKnapsack = (W, items) => {
  const n = items.length;
  const dp = Array(W + 1).fill(0); // DP table to store the max profit for each weight limit

  // Iterate over each item
  for (let i = 0; i < n; i++) {
    const { weight, profit } = items[i];

    // Traverse DP table forwards since items can be taken multiple times
    for (let w = weight; w <= W; w++) {
      dp[w] = Math.max(dp[w], dp[w - weight] + profit);
    }
  }

  return dp[W]; // Max profit for capacity W
}

// Example usage:
const itemsUnbounded = [
  { weight: 1, profit: 10 },
  { weight: 3, profit: 40 },
  { weight: 4, profit: 50 }
];
const WUnbounded = 6;
console.log(unboundedKnapsack(WUnbounded, itemsUnbounded)); // Output: 80
/* 
TC : O(N*W)
SC : O(W)
*/

Example​

Suppose you have items with weights [2, 3, 4] and values [4, 5, 6] and a knapsack capacity of 6:

  • 0/1 Knapsack: You can pick at most one of each item. The optimal solution is to select items with weights 2 and 4, giving a total value of 10.
  • Unbounded Knapsack: You can take multiple of the same item. The optimal solution is to take three items with weight 2 (since each gives 4 value), yielding a total value of 12.

Knapsack Problems on LeetCode

0/1 Knapsack Problems​

  1. Partition Equal Subset Sum (LC 416)
  2. Target Sum (LC 494)
  3. Ones and Zeroes (LC 474)
  4. Integer Break (LC 343)
  5. Combination Sum IV
  6. Subset Sum Problem
  7. Coin Change

Unbounded Knapsack Problems​

  1. Coin Change II (LC 518)
  2. Combination Sum IV (LC 377)
  3. Minimum Cost For Tickets (LC 983)
  4. House Robber (LC 198)
  5. House Robber II (LC 213)
  6. Burst Balloons (LC 312)
  7. Maximum Profit in Job Scheduling (LC 1235)
  8. Frog Jump (LC 403)

Interesting Follow-ups

Longest Decreasing Subsequence​

function lengthOfLDS(arr) {
  const n = arr.length;
  const dp = new Array(n).fill(1); // Initialize dp array

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

  // The length of the longest decreasing subsequence
  return Math.max(...dp);
}

Longest Increasing Subsequence in a 2D Matrix​

function longestIncreasingPath(matrix) {
  if (!matrix.length || !matrix[0].length) return 0;

  const rows = matrix.length;
  const cols = matrix[0].length;
  const dp = Array.from({ length: rows }, () => Array(cols).fill(-1)); // Memoization table

  // Directions for moving in the matrix (down, up, right, left)
  const directions = [
    [1, 0], // down
    [-1, 0], // up
    [0, 1], // right
    [0, -1] // left
  ];

  const isValid = (x, y, prevValue) => {
    return x >= 0 && x < rows && y >= 0 && y < cols && matrix[x][y] > prevValue;
  };

  const dfs = (x, y) => {
    if (dp[x][y] !== -1) return dp[x][y]; // Return already computed result

    let maxLength = 1; // The length of path starting from (x, y) is at least 1 (the cell itself)

    for (const [dx, dy] of directions) {
      const newX = x + dx;
      const newY = y + dy;

      if (isValid(newX, newY, matrix[x][y])) {
        maxLength = Math.max(maxLength, 1 + dfs(newX, newY));
      }
    }

    dp[x][y] = maxLength; // Memoize the result
    return maxLength;
  };

  let longestPath = 0;

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      longestPath = Math.max(longestPath, dfs(i, j));
    }
  }

  return longestPath;
}

// Example usage
const matrix = [
  [9, 9, 4],
  [6, 6, 8],
  [2, 1, 1]
];
console.log(longestIncreasingPath(matrix)); // Output: 4 (path: [1, 2, 6, 9])

Longest Bitonic Subsequence​

function lengthOfLBS(arr) {
    const n = arr.length;
    if (n === 0) return 0;

    // Step 1: Initialize LIS and LDS arrays
    const lis = new Array(n).fill(1);
    const lds = new Array(n).fill(1);

    // Step 2: Compute LIS for each element
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (arr[i] > arr[j]) {
                lis[i] = Math.max(lis[i], lis[j] + 1);
            }
        }
    }

    // Step 3: Compute LDS for each element
    for (let i = n - 2; i >= 0; i--) {
        for (let j = n - 1; j > i; j--) {
            if (arr[i] > arr[j]) {
                lds[i] = Math.max(lds[i], lds[j] + 1);
            }
        }
    }

    // Step 4: Calculate the maximum length of the bitonic subsequence
    let maxLength = 0;
    for (let i = 0; i < n; i++) {
        maxLength = Math.max(maxLength, lis[i] + lds[i] - 1);
    }

    return maxLength;
}

// Example usage
const arr = [1, 3, 5, 4, 7];
console.log(lengthOfLBS(arr)); // Output: 5 (subsequence: [1, 3, 5, 4, 1])