带你读《图解算法小抄》二十一、动态规划（7）https://developer.aliyun.com/article/1347956?groupCode=tech_library
下面是使用动态规划解决编辑距离问题的算法框架：
function minDistance(word1, word2) { const m = word1.length; const n = word2.length; 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 { dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1; } } } return dp[m][n]; }
14.打家劫舍 II
1）题目描述
给定一个代表每个房屋存放金额的非负整数数组，其中房屋被围成一圈。相邻的房屋在同一晚上被抢会触发警报系统。计算在不触发警报的情况下，你可以在这些房屋中抢劫到的最高金额。
2）解题步骤
为了计算在不触发警报的情况下能够抢劫到的最高金额，我们可以使用动态规划的思想来解决问题。
- 定义状态：我们可以将问题转化为对于每个房屋的状态，即该房屋被抢劫或不被抢劫。令 dp[i] 表示抢劫以第 i 个房屋结尾的子数组所能获得的最高金额。
- 初始状态：由于房屋被围成一圈，因此我们需要考虑首尾相连的情况。对于首尾相连的情况，我们有两种选择：
- 不抢劫第一个房屋，即将问题转化为抢劫第二个房屋到最后一个房屋的子数组，即 dp1[i]。
- 不抢劫最后一个房屋，即将问题转化为抢劫第一个房屋到倒数第二个房屋的子数组，即 dp2[i]。
- 状态转移方程：对于状态转移，我们可以分别考虑两种情况：
- 如果抢劫第 i 个房屋，那么前一个房屋不能被抢劫，因此最高金额为 dp[i-2] + nums[i]。
- 如果不抢劫第 i 个房屋，那么最高金额为 dp[i-1]。
- 综上所述，我们可以得到状态转移方程为 dp[i] = max(dp[i-2] + nums[i], dp[i-1])。
- 最终解：问题的解即为 max(dp1[n-2], dp2[n-1])，其中 n 是房屋的数量。
下面是使用动态规划解决打家劫舍 II 问题的算法框架：
function rob(nums) { const n = nums.length; if (n === 0) { return 0; } if (n === 1) { return nums[0]; } const dp1 = new Array(n).fill(0); const dp2 = new Array(n).fill(0); // 计算不抢劫第一个房屋的最高金额 dp1[0] = 0; dp1[1] = nums[1]; for (let i = 2; i < n; i++) { dp1[i] = Math.max(dp1[i - 2] + nums[i], dp1[i - 1]); } // 计算不抢劫最后一个房屋的最高金额 dp2[0] = nums[0]; dp2[1] = Math.max(nums[0], nums[1]); for (let i = 2; i < n - 1; i++) { dp2[i] = Math.max(dp2[i - 2] + nums[i], dp2[i - 1]); } return Math.max(dp1[n - 2], dp2[n - 2]); }
带你读《图解算法小抄》二十一、动态规划（9）https://developer.aliyun.com/article/1347954?groupCode=tech_library
