My Learning Blog

classic DP Algo-64,322,518,377,1143,300,368 - 3/16/2024

different kinds of dp

Grid DP

64:Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

function minPathSum(grid: number[][]): number {
  const m = grid.length;
  const n = grid[0].length;
  const dp = Array.from({ length: m }, () => new Array(n).fill(0));

  dp[0][0] = grid[0][0];

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

  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
    }
  }

  return dp[m - 1][n - 1];
}

Knapsack DP

To pinpoint a knapsack problem:

1.Check if the problem involves optimizing some value while staying within a constraint. This is the general requirement for a DP problem.

2.Check if there’s a constraint involving a combination of elements to fulfill a certain capacity. Look for terms such as “size”, “capacity”, “space available”, or “target”.

518:You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.

You may assume that you have an infinite number of each kind of coin.

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

  for (let i = 0; i < coins.length; i++) {
    for (let j = coins[i]; j <= amount; j++) {
      dp[j] += dp[j - coins[i]];
    }
  }

  return dp[amount];
}

322:You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

function coinChange(coins: number[], amount: number): number {
  const dp = new Array(amount + 1).fill(Infinity);
  // dp[j]: The current minimum number of coins needed to make up amount j.
  dp[0] = 0;
  for (let i = 0; i < coins.length; i++) {
    for (let j = coins[i]; j <= amount; j++) {
      dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
    }
  }

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

Initialize DP Array

You create an array dp of size amount + 1 and fill it with Infinity, except for dp[0], which you set to 0. The reason for setting dp[0] to 0 is that it takes 0 coins to make up an amount of 0. The Infinity values are used to indicate that, initially, it’s considered impossible to make up those amounts.

Dynamic Programming Loop

You iterate over each coin in the coins array. For each coin, you iterate through all possible amounts from that coin’s value up to the target amount. For each amount j, you update dp[j] to be the minimum of its current value and dp[j - coins[i]] + 1. This update reflects taking the minimum between not using the current coin at all or using one instance of the current coin plus the minimum number of coins needed to make up the remaining amount (j - coins[i]).

dp[j]: The current minimum number of coins needed to make up amount j.

dp[j - coins[i]] + 1: The number of coins needed if you include the current coin. The +1 accounts for using one coin of the current denomination.

Check and Return: Finally

check if dp[amount] is still Infinity. If it is, this means it was impossible to make up the amount with the given coins, and you return -1. Otherwise, you return dp[amount], which now contains the minimum number of coins needed to make up the amount.

This function efficiently solves the Coin Change problem, ensuring that the minimum number of coins needed to make up any amount (if possible) is calculated. By iterating over the coins and updating the DP array, it finds the optimal combination of coins for each amount up to the target amount.

377:Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

Note that different sequences are counted as different combinations.

function combinationSum4(nums: number[], target: number): number {
  const dp = new Array(target + 1).fill(0);
  dp[0] = 1;

  for (let j = 0; j <= target; j++) {
    for (const item of nums) {
      if (j >= item) {
        dp[j] = dp[j] + dp[j - item];
      }
    }
  }

  return dp[target];
}

Dual-Sequence DP

Dual-sequence dynamic programming (DP) focuses on solutions derived from two linear sequences, such as arrays or strings. These problems mainly aim to compute a value concerning both sequences. A notable feature of numerous DP problems is their dependence on sequence prefixes.

1143:Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

function longestCommonSubsequence(text1: string, text2: string): number {
  const m: number = text1.length;
  const n: number = text2.length;
  const dp: number[][] = Array.from({ length: m + 1 }, () =>
    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];
}

Initializing the DP Array

Initialize a 2D array dp of size (m + 1) x (n + 1), where m and n are the lengths of text1 and text2, respectively. Each dp[i][j] represents the length of the longest common subsequence of the substrings text1[0..i-1] and text2[0..j-1].

dp[i][0] and dp[0][j] are initialized to 0 for all i and j, representing the base cases where one of the strings is empty, so the LCS length is 0.

Filling the DP Table

You then fill the DP table row by row and column by column, starting from dp[1][1]. For each pair of indices (i, j), you check if the characters at text1[i - 1] and text2[j - 1] are the same.

If they are the same, it means that these characters are part of the LCS, so you set dp[i][j] to dp[i - 1][j - 1] + 1. This is because the LCS at this point includes the LCS up to text1[i - 2] and text2[j - 2], plus the matching character.

If they are not the same, you set dp[i][j] to the maximum of dp[i - 1][j] and dp[i][j - 1]. This represents the fact that the LCS up to text1[i-1] and text2[j-1] is the longer of the LCSs found by either omitting the last character of text1 or omitting the last character of text2.

Returning the Result

The value in dp[m][n] at the end of the algorithm contains the length of the LCS of text1 and text2, which is the final result.

This approach efficiently solves the problem by ensuring that each subproblem is only solved once and that its solution is used to solve larger subproblems, leading to an overall polynomial time complexity of O(m*n), where m and n are the lengths of the input strings.

Dynamic number of subproblems

300:Given an integer array nums, return the length of the longest strictly increasing subsequence.

function lengthOfLIS(nums: number[]): number {
  const m = nums.length;
  const dp = new Array(m).fill(1);

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

  return Math.max(...dp);
}

368:Largest Divisible Subset Given a set of distinct positive integers nums, return the largest subset answer such that every pair (answer[i], answer[j]) of elements in this subset satisfies:

answer[i] % answer[j] == 0, or answer[j] % answer[i] == 0 If there are multiple solutions, return any of them.

function largestDivisibleSubset(nums: number[]): number[] {
  nums.sort((a, b) => a - b);
  const dp = new Array(nums.length).fill(1);
  const pre = new Array(nums.length).fill(-1);

  let maxLen = 1;
  let maxIdx = 0; //Record the position of the last element in the largest divisible subset
  for (let i = 0; i < nums.length; i++) {
    const lastItem = nums[i];
    for (let j = 0; j < i; j++) {
      if (lastItem % nums[j] == 0 && dp[j] + 1 > dp[i]) {
        dp[i] = dp[j] + 1;
        pre[i] = j;
      }
    }

    if (dp[i] > maxLen) {
      maxLen = dp[i];
      maxIdx = i;
    }
  }
  // if you don't want to use if block to update the maxLen and maxIdx,you can do below:
  // const maxLen = Math.max(...dp)
  // const maxIdx = dp.indexOf(maxLen)
  const res = [];
  while (maxIdx !== -1) {
    res.push(nums[maxIdx]);
    maxIdx = pre[maxIdx];
  }

  return res;
}

139:word break

function wordBreak(s: string, wordDict: string[]): boolean {
  const wordSet = new Set(wordDict);
  //  dp[i] will be true if the substring s[0...i-1] can be segmented into dictionary words.
  const dp: boolean[] = Array(s.length + 1).fill(false);
  dp[0] = true; // Base case: empty string

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

  return dp[s.length];
}

1.Create an array dp where dp[i] will be true if the substring s[0…i-1] can be segmented into dictionary words.

2.Initialize dp[0] = true, indicating that an empty string can always be segmented.

3.For each index i from 1 to length of s, check every possible substring s[j…i-1] (where j < i). If dp[j] is true and the substring s[j…i-1] is in the dictionary, set dp[i] to true.

4.The value of dp[length of s] gives the answer.