Dynamic programming

The Three Steps of Dynamic Programming#

Dynamic programming is essentially using historical records to avoid repetitive calculations. These historical records are stored in variables, usually in one-dimensional or two-dimensional arrays.

Step 1: Define the meaning of array elements. As mentioned earlier, historical records are usually stored in arrays. Let's assume we use a one-dimensional array dp[]. The meaning of each array element is very important.

Step 2: Find the relationship between array elements. Dynamic programming is similar to the mathematical induction we learned in high school. We can use dp[n-1], dp[n-2], ..., dp[1] to deduce dp[n]. In other words, we can use historical data to derive new element values. Therefore, we need to find the relationship between array elements, such as dp[n] = dp[n-1] + dp[n-2], which is the relationship between them.

Step 3: Find the initial values. Even if we know the relationship between array elements, we still need initial values to deduce dp[n].

Frog Jumping Stairs#

A frog can jump either 1 step or 2 steps at a time. How many different ways are there for the frog to jump to the nth step?

Define the meaning of array elements: There are dp[i] ways for the frog to jump to the ith step. Our goal is to find dp[n].
Find the relationship between array elements: For this problem, since the frog can choose to jump one step or two steps, there are two ways for the frog to reach the ith step: one is to jump from the (i-1)th step, and the other is to jump from the (i-2)th step. Therefore, the total number of ways to jump to the ith step is dp[i] = dp[i-1] + dp[i-2].
Find the initial values: dp[0] = 0; dp[1] = 1; dp[2] = 2;

The solution code is as follows:

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

console.log(f(2)) // 2
console.log(f(3)) // 3
console.log(f(4)) // 5
console.log(f(5)) // 8

Unique Paths#

Problem source: Unique Paths

A robot is located at the top-left corner of a m x n grid. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid. How many possible unique paths are there?

Define the meaning of array elements: We can view the grid as a two-dimensional array. The starting point is at coordinates (0,0), and the bottom-right corner is at coordinates (m-1)(n-1). When the robot reaches position (i,j), there are dp[i][j] possible paths. Our goal is to find dp[m-1][n-1].
Find the relationship between array elements: To reach position (i,j), there are two ways: one is to come from position (i-1,j), and the other is to come from position (i,j-1). Therefore, the total number of ways to reach position (i,j) is dp[i][j] = dp[i-1][j] + dp[i][j-1].
Find the initial values: It is easy to see that when i=0 or j=0, the robot can only move right or down, and there is only one way.

The solution code is as follows:

var uniquePaths = function (m, n) {
  if (m <= 0 || n <= 0) {
    return 0
  }

  // Initialize the two-dimensional array
  const dp = new Array(m).fill(0).map((_) => new Array(n).fill(0))
  // When there is only one column
  for (let i = 0; i < m; i++) {
    dp[i][0] = 1
  }
  // When there is only one row
  for (let j = 0; j < n; j++) {
    dp[0][j] = 1
  }

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

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

console.log(uniquePaths(3, 2)) // 3
console.log(uniquePaths(3, 3)) // 6
console.log(uniquePaths(2, 1)) // 1

Minimum Path Sum#

Problem source: Minimum Path Sum

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

Define the meaning of array elements: We can view the grid as a two-dimensional array. The starting point is at coordinates (0,0), and the bottom-right corner is at coordinates (m-1)(n-1). When we walk from the top left to position (i,j), the minimum path sum is dp[i][j]. Our goal is to find dp[m-1][n-1].
Find the relationship between array elements: To reach position (i,j), there are two ways: one is to come from position (i-1,j), and the other is to come from position (i,j-1). Therefore, the minimum path sum is dp[i][j] = Math.min(dp[i - 1][j] + arr[i][j], dp[i][j - 1] + arr[i][j]).
Find the initial values: It is easy to see that when i=0 or j=0, we can only move right or down, and there is only one path with the minimum path sum.

The solution code is as follows:

var minPathSum = function (grid) {
  const m = grid.length,
    n = grid[0].length

  if (m <= 0 || n <= 0) {
    return 0
  }

  const dp = new Array(m).fill(0).map((_) => new Array(n).fill(0))

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

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

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

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

const grid = [
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1],
]

console.log(minPathSum(grid)) // 7  The minimum path sum is achieved by the path 1→3→1→1→1

Edit Distance#

Problem source: Edit Distance

Given two words word1 and word2, return the minimum number of operations required to convert word1 to word2. You have the following three operations permitted on a word:

Insert a character

Delete a character

Replace a character

Define the meaning of array elements: When the length of word1 is i and the length of word2 is j, the minimum number of operations required to convert word1 to word2 is dp[i][j].
Find the relationship between array elements: In most cases, dp[i][j] definitely has a relationship with dp[i-1][j], dp[i][j-1], and dp[i-1][j-1]. In this problem, we find the relationship as follows:
If word1[i] is equal to word2[j], there is no need to perform any operations, so we have dp[i][j] = dp[i-1][j-1].
If word1[i] is not equal to word2[j], there are three operations to consider, and we need to find the minimum value among these three operations: dp[i][j] = min(dp[i-1][j-1],dp[i][j-1],dp[[i-1][j]]) + 1:
1. If we replace the character word1[i] with word2[j], we have dp[i][j] = dp[i-1][j-1] + 1.
2. If we insert a character at the end of word1 that is equal to word2[j], we have dp[i][j] = dp[i][j-1] + 1.
3. If we delete the character word1[i], we have dp[i][j] = dp[i-1][j] + 1.
Find the initial values: In dp[i][j], if i or j is 0, i-1 or j-1 will be negative, so we need to calculate the initial values for all cases where i or j is 0.

The solution code is as follows:

var minDistance = function (word1, word2) {
  const m = word1.length,
    n = word2.length
  const dp = new Array(m).fill(0).map((_) => new Array(n).fill(0))
  dp[0][0] = 0

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

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

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      // Note that the index of the i-th character is i-1
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1]
      } else {
        dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1
      }
    }
  }
  return dp[m][n]
}

console.log(minDistance('horse', 'ros')) // 3