Comment on page
03 动态规划
动态规划，无非就是利用历史记录，来避免我们的重复计算。而这些历史记录，我们得需要一些变量来保存，一般是用一维数组或者二维数组来保存。
**步骤一：定义数组元素的含义。**前面提到一般用数组来保存历史记录，假设用一维数组 dp[]，这时候每个数组元素的含义非常重要。
**步骤二：找出数组元素之间的关系式。**动态规划类似于我们高中学习时的归纳法，可以利用 dp[n-1]、dp[n-2]...dp[1]，进而推出 dp[n]，也就是可以利用历史数据来推出新的元素值，所以我们要找出数组元素之间的关系式，例如 dp[n] = dp[n-1] + dp[n-2]，这个就是他们的关系式了。
**步骤三：找出初始值。**即便知道了数组元素之间的关系式，也需要根据初始值才能推导出 dp[n]。
一只青蛙一次可以跳上 1 级台阶，也可以跳上 2 级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
- 1.定义数组元素的含义：跳上一个 i 级的台阶总共有 dp[i] 种跳法，我们的目标是求 dp[n]。
- 2.找出数组元素之间的关系式：对于这道题，由于情况可以选择跳一级，也可以选择跳两级，所以青蛙到达第 i 级的台阶有两种方式：一种是从第 i-1 级跳上来，一种是从第 i-2 级跳上来，所以所有可能的跳法的 dp[i] = dp[i-1] + dp[i-2]。
- 3.找出初始值：dp[0] = 0; dp[1] = 1; dp[3] = 3;
得出求解代码：
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
一个机器人位于一个 m x n 网格的左上角。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。问总共有多少条不同的路径？
- 1.定义数组元素的含义：我们把网格看作一个二维数组，起点坐标为 (0,0)，右下角坐标为 (m-1)(n-1)，当机器人从左上角走到 (i,j) 这个位置时，一共有
dp[i][j]种路径，所以我们的目标是求dp[m-1][n-1]。 - 2.找出数组元素之间的关系式：达到 (i,j) 这个位置有两种方式：一种是从 (i-1,j) 这个位置到达，一种是从 (i,j-1) 这个位置到达，所以所有达到的方式
dp[i][j] = dp[i-1][j] + dp[i][j-1]。 - 3.找出初始值：可以易知，当 i=0 或者 j=0 时，只能往右或者往下，方式只有一种。
得出求解代码：
var uniquePaths = function (m, n) {
if (m <= 0 || n <= 0) {
return 0
}
// 初始化二维数组
const dp = new Array(m).fill(0).map((_) => new Array(n).fill(0))
// 当只有一列时
for (let i = 0; i < m; i++) {
dp[i][0] = 1
}
// 当只有一行时
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
给定一个包含非负整数的 m x n 网格，每次只能向下或者向右移动一步，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
- 1.定义数组元素的含义：我们把网格看作一个二维数组，起点坐标为 (0,0)，右下角坐标为 (m-1)(n-1)，当从左上角走到 (i,j) 这个位置时，最小路径和为
dp[i][j]，所以我们的目标是求dp[m-1][n-1]。 - 2.找出数组元素之间的关系式：达到 (i,j) 这个位置有两种方式：一种是从 (i-1,j) 这个位置到达，一种是从 (i,j-1) 这个位置到达，所以最小路径和
dp[i][j] = Math.min(dp[i - 1][j] + arr[i][j], dp[i][j - 1] + arr[i][j])。 - 3.找出初始值：可以易知，当 i=0 或者 j=0 时，只能往右或者往下，方式只有一种，最小路径和也只有一种。
得出求解代码：
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]
// 最左边的列
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] = 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 路径 1→3→1→1→1 的总和最小
给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作： 插入一个字符 删除一个字符 替换一个字符
- 1.定义数组元素的含义：当字符串 word1 的长度为 i，字符串 word2 的长度为 j 时，将 word1 转化为 word2 所使用的最少操作次数为
dp[i][j]。 - 2.找出数组元素之间的关系式：大部分情况下，
dp[i][j]和dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]肯定存在某种关系。这题中，我们找出其中关系如下：- 如果 word1[i] 与 word2[j] 相等，这个时候不需要进行任何操作，显然有
dp[i][j] = dp[i-1][j-1]。 - 如果 word1[i] 与 word2[j] 不相等，则有三种操作，我们需要找出这三种操作的最小值，则
dp[i][j] = min(dp[i-1][j-1],dp[i][j-1],dp[[i-1][j]]) + 1：- 1.如果把字符 word1[i] 替换成与 word2[j] 后相等，则有
dp[i][j] = dp[i-1][j-1] + 1 - 2.如果在字符串 word1 末尾插入一个与 word2[j] 相等的字符，则有
dp[i][j] = dp[i][j-1] + 1 - 3.如果把字符 word1[i] 删除，则有
dp[i][j] = dp[i-1][j] + 1
- 3.找出初始值：当
dp[i][j]中，如果 i 或者 j 有一个为 0，i-1 或 j-1 则为负数，所以初始值需要先计算出所有 i 或 j 为 0 的情况。
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++) {
// 注意第 i 个字符的下标是 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
最近更新 10mo ago