Reference article: 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`

:- If we replace the character word1[i] with word2[j], we have
`dp[i][j] = dp[i-1][j-1] + 1`

. - 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`

. - If we delete the character word1[i], we have
`dp[i][j] = dp[i-1][j] + 1`

.

- If we replace the character word1[i] with word2[j], we have
- 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
```