动态规划的常用状态转移方程总结
文章目录
- 动态规划的常用状态转移方程总结
- 1.斐波那契数列
- 1. 斐波那契数列定义
- 2. 动态规划方程
- 2.爬楼梯问题
- 1. 爬楼梯问题定义
- 2.动态规划方程
- 3.背包问题
- 1. 背包问题定义
- 2. 动态规划方程
- 4.最长递增子序列
- 1. 最长递增子序列定义
- 2. 动态规划方程
- 5.最大子数组和
- 1. 最大子数组和定义
- 2. 动态规划方程
- 6.最长公共子序列
- 1. 最长公共子序列定义
- 2. 动态规划方程
- 7.编辑距离
- 1. 编辑距离定义
- 2. 动态规划方程
- 8.打家劫舍
- 1. 打家劫舍问题定义
- 2. 动态规划方程
- 9.最大正方形
- 1. 最大正方形定义
- 2. 动态规划方程
1.斐波那契数列
1. 斐波那契数列定义
斐波那契数列是一个经典的数学数列，其中每个数字是前两个数字的和。通常，斐波那契数列的前几个数字是：1, 1, 2, 3, 5, 8, 13, 21, …
2. 动态规划方程
动态规划的转移方程为 dp[i] = dp[i-1] + dp[i-2]，其中 dp[i] 表示第 i 个斐波那契数。
// 定义一个函数，接受斐波那契数列的序号作为参数 function fibonacci(n) { // 初始化一个数组dp，用于存储斐波那契数列的值 const dp = []; // 初始条件：第0个和第1个斐波那契数都为1 dp[0] = dp[1] = 1; // 通过动态规划的转移方程计算每个斐波那契数 for (let i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } // 返回第n个斐波那契数 return dp[n]; } // 测试例子 const n = 5; const result = fibonacci(n); console.log(`第${n}个斐波那契数为：${result}`); //第5个斐波那契数为：8 数组[5] 1 1 2 3 5 8- fibonacci 函数接受一个参数 n，表示要计算第 n 个斐波那契数。
- 初始化一个数组 dp，用于存储斐波那契数列的值。
- 初始条件设置 dp[0] 和 dp[1] 均为 1，作为数列的起始。
- 通过循环计算每个斐波那契数，根据动态规划的转移方程 dp[i] = dp[i-1] + dp[i-2]。
- 最后返回第 n 个斐波那契数。
2.爬楼梯问题
1. 爬楼梯问题定义
爬楼梯问题是一个经典的动态规划问题，其目标是计算爬到第 n 级楼梯的方法数，每次可以爬 1 或 2 级楼梯。动态规划的转移方程为 dp[i] = dp[i-1] + dp[i-2]，其中 dp[i] 表示爬到第 i 级楼梯的方法数。
2.动态规划方程
dp[i] = dp[i-1] + dp[i-2]，其中 dp[i] 表示爬到第 i 级楼梯的方法数。
// 定义一个函数，接受楼梯的级数作为参数 function climbStairs(n) { // 初始化一个数组dp，用于存储到达每一级楼梯的方法数 const dp = []; // 初始条件：爬到第0级和第1级楼梯的方法数都为1 dp[0] = dp[1] = 1; // 通过动态规划的转移方程计算每一级楼梯的方法数 for (let i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } // 返回爬到第n级楼梯的方法数 return dp[n]; } // 测试例子 const n = 4; const result = climbStairs(n); console.log(`爬到第${n}级楼梯的方法数为：${result}`); //爬到第4级楼梯的方法数为：5 当 n=4 时，输出结果是 5，表示爬到第 4 级楼梯有 5 种不同的方式。这包括： 1 步 + 1 步 + 1 步 + 1 步 2 步 + 1 步 + 1 步 1 步 + 2 步 + 1 步 1 步 + 1 步 + 2 步 2 步 + 2 步- climbStairs 函数接受一个参数 n，表示楼梯的级数。
- 初始化一个数组 dp，用于存储到达每一级楼梯的方法数。
- 初始条件设置 dp[0] 和 dp[1] 均为 1，作为楼梯的起始条件。
- 通过循环计算每一级楼梯的方法数，根据动态规划的转移方程 dp[i] = dp[i-1] + dp[i-2]。
- 最后返回爬到第 n 级楼梯的方法数。
3.背包问题
1. 背包问题定义
背包问题是一个经典的动态规划问题，目标是在给定背包容量下，选择一定数量的物品放入背包，使得放入背包的物品总价值最大。这里采用的是 0/1 背包问题，即每个物品只能选择放入一次或不放入。
2. 动态规划方程
动态规划的转移方程为 dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])，其中 dp[i][j] 表示在前 i 个物品中选择总重量不超过 j 的最大价值，weight[i] 表示第 i 个物品的重量，value[i] 表示第 i 个物品的价值。
// 定义一个函数，接受物品的重量数组和价值数组以及背包的容量作为参数 function knapsackProblem(weights, values, capacity) { const n = weights.length; // 物品的数量 // 初始化一个二维数组dp，表示在前i个物品中选择总重量不超过j的最大价值 const dp = new Array(n + 1).fill(0).map(() => new Array(capacity + 1).fill(0)); // 动态规划，计算每个子问题的最优解 for (let i = 1; i <= n; i++) { for (let j = 1; j <= capacity; j++) { // 当前物品的重量 const currentWeight = weights[i - 1]; // 当前物品的价值 const currentValue = values[i - 1]; // 如果当前物品的重量小于等于背包的容量 if (currentWeight <= j) { // 选择当前物品或不选择当前物品，取较大的价值 dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - currentWeight] + currentValue); } else { // 如果当前物品的重量大于背包的容量，则不能选择当前物品 dp[i][j] = dp[i - 1][j]; } } } // 返回在前n个物品中选择总重量不超过capacity的最大价值 return dp[n][capacity]; } // 测试例子 const weights = [2, 1, 3]; const values = [4, 2, 3]; const capacity = 4; const result = knapsackProblem(weights, values, capacity); console.log(`在给定容量为${capacity}的背包中，能够获得的最大价值为：${result}`); //在给定容量为4的背包中，能够获得的最大价值为：6- knapsackProblem 函数接受三个参数：物品的重量数组 weights、价值数组 values，以及背包的容量 capacity。
- 初始化一个二维数组 dp，用于存储在前 i 个物品中选择总重量不超过 j 的最大价值。
- 通过嵌套循环计算每个子问题的最优解，根据动态规划的转移方程更新 dp 数组。
- 最后返回在前 n 个物品中选择总重量不超过 capacity 的最大价值。
4.最长递增子序列
1. 最长递增子序列定义
最长递增子序列是指在一个数组中找到一个子序列，使得这个子序列中的元素是按照升序排列的，并且在所有符合条件的子序列中它是最长的。
2. 动态规划方程
动态规划的转移方程为 dp[i] = max(dp[j] + 1, dp[i])，其中 dp[i] 表示以第 i 个元素结尾的最长递增子序列的长度，j 为 0 到 i-1 的索引，且 nums[i] > nums[j]。
// 定义一个函数，接受数组作为参数 function longestIncreasingSubsequence(nums) { const n = nums.length; // 数组的长度 // 初始化一个数组dp，表示以第i个元素结尾的最长递增子序列的长度 const dp = new Array(n).fill(1); // 动态规划，计算每个子问题的最优解 for (let i = 1; i < n; i++) { for (let j = 0; j < i; j++) { // 如果当前元素大于前面某个元素，则更新最长递增子序列的长度 if (nums[i] > nums[j]) { dp[i] = Math.max(dp[j] + 1, dp[i]); } } } // 返回最长递增子序列的最大长度 return Math.max(...dp); } // 测试例子 const nums = [10, 22, 9, 33, 21, 50, 41, 60, 80]; const result = longestIncreasingSubsequence(nums); console.log(`最长递增子序列的长度为：${result}`); //最长递增子序列的长度为：6- longestIncreasingSubsequence 函数接受一个数组 nums 作为参数。
- 初始化一个数组 dp，用于存储以每个元素结尾的最长递增子序列的长度，初始值为1。
- 动态规划通过两层循环计算每个子问题的最优解。
- 如果当前元素 nums[i] 大于前面某个元素 nums[j]，则更新最长递增子序列的长度 dp[i] 为当前的最大值。
- 最后返回最长递增子序列的最大长度，使用 Math.max(...dp) 获取数组中的最大值。
5.最大子数组和
1. 最大子数组和定义
最大子数组和问题是一个经典的动态规划问题，其目标是找到一个具有最大和的连续子数组。
2. 动态规划方程
动态规划的转移方程为 dp[i] = max(nums[i], nums[i] + dp[i-1])，其中 dp[i] 表示以第 i 个元素结尾的最大子数组和。
// 定义一个函数，接受数组作为参数 function maxSubArray(nums) { const n = nums.length; // 数组的长度 // 初始化一个数组dp，表示以第i个元素结尾的最大子数组和 const dp = new Array(n); // 初始条件：第0个元素结尾的最大子数组和即为第0个元素本身 dp[0] = nums[0]; // 动态规划，计算每个子问题的最优解 for (let i = 1; i < n; i++) { // 当前元素单独构成子数组，或者与前面的子数组连接 dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]); } // 返回以每个元素结尾的最大子数组和中的最大值 return Math.max(...dp); } // 测试例子 const nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]; const result = maxSubArray(nums); console.log(`最大子数组和为：${result}`); //最大子数组和为：6- maxSubArray 函数接受一个数组 nums 作为参数。
- 初始化一个数组 dp，用于存储以每个元素结尾的最大子数组和。
- 初始条件设置 dp[0] 为第0个元素本身。
- 动态规划通过循环计算每个子问题的最优解，即以当前元素结尾的最大子数组和。
- 转移方程 dp[i] = max(nums[i], nums[i] + dp[i-1]) 表示当前元素单独构成子数组，或者与前面的子数组连接，取两者中的较大值。
- 最后返回以每个元素结尾的最大子数组和中的最大值，使用 Math.max(...dp) 获取数组中的最大值。
6.最长公共子序列
1. 最长公共子序列定义
最长公共子序列是指在两个字符串中找到一个最长的子序列，使得它在两个字符串中都出现，但不要求连续。
2. 动态规划方程
动态规划的转移方程为：
- 如果 str1[i] 等于 str2[j]，则 dp[i][j] = dp[i-1][j-1] + 1；
- 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])，其中 dp[i][j] 表示 str1 的前 i 个字符和 str2 的前 j 个字符的最长公共子序列的长度。
// 定义一个函数，接受两个字符串作为参数 function longestCommonSubsequence(str1, str2) { const m = str1.length; // 字符串1的长度 const n = str2.length; // 字符串2的长度 // 初始化一个二维数组dp，表示str1的前i个字符和str2的前j个字符的最长公共子序列的长度 const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0)); // 动态规划，计算每个子问题的最优解 for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { // 如果当前字符相等，则取左上方的值加1 if (str1[i - 1] === str2[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]); } } } // 返回str1的前m个字符和str2的前n个字符的最长公共子序列的长度 return dp[m][n]; } // 测试例子 const str1 = "abcde"; const str2 = "ace"; const result = longestCommonSubsequence(str1, str2); console.log(`最长公共子序列的长度为：${result}`); //最长公共子序列的长度为：3- longestCommonSubsequence 函数接受两个字符串 str1 和 str2 作为参数。
- 初始化一个二维数组 dp，用于存储str1的前i个字符和str2的前j个字符的最长公共子序列的长度。
- 动态规划通过两层循环计算每个子问题的最优解。
- 转移方程中，如果当前字符相等，则取左上方的值加1；如果当前字符不相等，则取左方和上方的最大值。
- 最后返回 str1 的前 m 个字符和 str2 的前 n 个字符的最长公共子序列的长度，即 dp[m][n]。
7.编辑距离
1. 编辑距离定义
编辑距离是衡量两个字符串相似程度的一种指标，表示将一个字符串转换成另一个字符串所需的最少操作次数。典型的操作包括插入一个字符、删除一个字符、替换一个字符。
2. 动态规划方程
动态规划的转移方程为：
- 如果 word1[i] 等于 word2[j]，则 dp[i][j] = dp[i-1][j-1]；
- 否则，dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1，其中 dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作次数。
// 定义一个函数，接受两个单词作为参数 function minDistance(word1, word2) { const m = word1.length; // 单词1的长度 const n = word2.length; // 单词2的长度 // 初始化一个二维数组dp，表示将word1的前i个字符转换为word2的前j个字符所需的最少操作次数 const dp = new Array(m + 1).fill(0).map(() => new Array(n + 1).fill(0)); // 初始化边界条件 for (let i = 0; i <= m; i++) { dp[i][0] = i; } for (let j = 0; j <= n; j++) { dp[0][j] = j; } // 动态规划，计算每个子问题的最优解 for (let i = 1; i <= m; i++) { for (let j = 1; j <= n; j++) { // 如果当前字符相等，则取左上方的值 if (word1[i - 1] === word2[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { // 如果当前字符不相等，则取左方、上方和左上方的最小值加1 dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1; } } } // 返回将word1的前m个字符转换为word2的前n个字符所需的最少操作次数 return dp[m][n]; } // 测试例子 const word1 = "horse"; const word2 = "ros"; const result = minDistance(word1, word2); console.log(`将"${word1}"转换为"${word2}"所需的最少操作次数为：${result}`); //将"horse"转换为"ros"所需的最少操作次数为：3- minDistance 函数接受两个单词 word1 和 word2 作为参数。
- 初始化一个二维数组 dp，用于表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最少操作次数。
- 初始化边界条件，即当一个字符串为空时，转换所需的操作次数为字符串的长度。
- 动态规划通过两层循环计算每个子问题的最优解。
- 转移方程中，如果当前字符相等，则取左上方的值；如果当前字符不相等，则取左方、上方和左上方的最小值加1。
- 最后返回将 word1 的前 m 个字符转换为 word2 的前 n 个字符所需的最少操作次数，即 dp[m][n]。
8.打家劫舍
1. 打家劫舍问题定义
打家劫舍问题是一个典型的动态规划问题，目标是在一排房屋中选择一些房屋进行偷窃，但不能偷相邻的房屋，求能够获得的最大金额。
2. 动态规划方程
动态规划的转移方程为 dp[i] = max(dp[i-1], dp[i-2] + nums[i])，其中 dp[i] 表示前 i 个房屋能够获得的最大金额，nums[i] 表示第 i 个房屋中的金额。
// 定义一个函数，接受一个包含每个房屋金额的数组作为参数 function rob(nums) { const n = nums.length; // 房屋的数量 if (n === 0) { return 0; // 没有房屋，则返回0 } else if (n === 1) { return nums[0]; // 只有一个房屋，则返回该房屋的金额 } // 初始化一个数组dp，表示前i个房屋能够获得的最大金额 const dp = new Array(n); // 前两个房屋的最大金额为较大的那个 dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]); // 动态规划，计算每个子问题的最优解 for (let i = 2; i < n; i++) { // 在偷第i个房屋和不偷第i个房屋之间取较大值 dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]); } // 返回前n个房屋能够获得的最大金额 return dp[n - 1]; } // 测试例子 const nums = [2, 7, 9, 3, 1]; const result = rob(nums); console.log(`在给定房屋中能够获得的最大金额为：${result}`); //在给定房屋中能够获得的最大金额为：12- rob 函数接受一个包含每个房屋金额的数组 nums 作为参数。
- 根据房屋的数量 n 分情况处理：如果没有房屋，则返回0；如果只有一个房屋，则返回该房屋的金额。
- 初始化一个数组 dp，表示前 i 个房屋能够获得的最大金额。
- 前两个房屋的最大金额为较大的那个，即 dp[0] = nums[0] 和 dp[1] = Math.max(nums[0], nums[1])。
- 动态规划通过循环计算每个子问题的最优解，转移方程为 dp[i] = max(dp[i-1], dp[i-2] + nums[i])，表示在偷第 i 个房屋和不偷第 i 个房屋之间取较大值。
- 最后返回前 n 个房屋能够获得的最大金额，即 dp[n - 1]。
9.最大正方形
1. 最大正方形定义
最大正方形是指在一个二维矩阵中，由’1’组成的最大正方形的边长。
2. 动态规划方程
动态规划的转移方程为：
- 如果 matrix[i][j] 等于 1，则 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1；
- 否则，dp[i][j] = 0，其中 dp[i][j] 表示以 matrix[i][j] 为右下角的最大正方形的边长。
// 定义一个函数，接受一个包含0和1的二维矩阵作为参数 function maximalSquare(matrix) { const m = matrix.length; // 矩阵的行数 const n = matrix[0].length; // 矩阵的列数 // 初始化一个二维数组dp，表示以matrix[i][j]为右下角的最大正方形的边长 const dp = new Array(m).fill(0).map(() => new Array(n).fill(0)); // 初始化结果，表示最大正方形的边长 let maxSquare = 0; // 动态规划，计算每个子问题的最优解 for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { // 如果当前元素为1，则更新dp[i][j]为左、上、左上三个方向的最小值加1 if (matrix[i][j] === '1') { dp[i][j] = Math.min( i > 0 ? dp[i - 1][j] : 0, j > 0 ? dp[i][j - 1] : 0, i > 0 && j > 0 ? dp[i - 1][j - 1] : 0 ) + 1; // 更新最大正方形的边长 maxSquare = Math.max(maxSquare, dp[i][j]); } } } // 返回最大正方形的边长的平方 return maxSquare * maxSquare; } // 测试例子 const matrix = [ ['1', '0', '1', '0', '0'], ['1', '0', '1', '1', '1'], ['1', '1', '1', '1', '1'], ['1', '0', '0', '1', '0'] ]; const result = maximalSquare(matrix); console.log(`最大正方形的面积为：${result}`); //最大正方形的面积为：4- maximalSquare 函数接受一个包含0和1的二维矩阵 matrix 作为参数。
- 初始化一个二维数组 dp，用于存储以 matrix[i][j] 为右下角的最大正方形的边长。
- 初始化结果 maxSquare，表示最大正方形的边长。
- 动态规划通过两层循环计算每个子问题的最优解。
- 转移方程中，如果当前元素为1，则更新 dp[i][j] 为左、上、左上三个方向的最小值加1；否则， dp[i][j] 为0。
- 在动态规划过程中，不断更新最大正方形的边长。
- 最后返回最大正方形的边长的平方，即 maxSquare * maxSquare。