Loading... # 打家劫舍 定义 dp[i] 为前 i 个房子抢到的最大金额，那么有 $dp[i] = max(dp[i-1], dp[i-2] + nums[i])$ ```go func rob(nums []int) int { n := len(nums) if n == 1 { return nums[0] } dp := make([]int, n) dp[0] = nums[0] dp[1] = max(nums[0], nums[1]) for i := 2; i < n; i++ { dp[i] = max(dp[i-1], dp[i-2]+nums[i]) } return dp[n-1] } ``` # 跳跃游戏II 这道题相当于比跳跃游戏I多了个每一节能跳多少格的扩展限制，其实我们定义 dp[i] 为到达该格的最小步数后，还是很简单的就知道怎么推导出步数。 首先站在第 i 格，可以跳到i+1..i+j 的任意一个格子 所以第 i 格可以对第 i+j 格提供一条路，或者选择它本身的值，所以只需要初始化每个 dp 为 n+1（不可能的步数），就可以逐步缩小范围得到答案。 ```go func jump(nums []int) int { n := len(nums) dp := make([]int, n) for i := range dp { dp[i] = n + 1 } dp[0] = 0 for i, v := range nums { for j := 1; j <= v && i+j < n; j++ { dp[i+j] = min(dp[i+j], dp[i]+1) } } return dp[n-1] } ``` # 预测赢家 这道题主要是需要理清递推公式，首先定义 dp[i][j] 是 nums[i..j] 的先手对于后手的优势分数，那么我们就有如下关系： $dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])$ 这个公式其实就是先手选择了首尾中某一个值后，后手对其造成的损失就是从剩下的中选择的最优解，相当于把后手看作了减掉当前数字后的先手，这样一个巧妙地关系转化，便能递推出全部的结果。 首先初始值我们知道 $dp[i][i] = nums[i]$ 所以只需要外层循环以长度为基准，内层从 0 开始递推，也就是从左上角往右下角逐步的转化，就可以得到最终解 dp[0][n-1] >= 0 ```go func predictTheWinner(nums []int) bool { n := len(nums) // dp[i][j] = nums[i..j] 先手的优势分数 dp := make([][]int, n) for i := range dp { dp[i] = make([]int, n) // 只取一个数的优势分数 dp[i][i] = nums[i] } for length := 2; length <= n; length++ { for i := 0; i + length - 1 < n; i++ { j := i + length - 1 dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]) } } return dp[0][n-1] >= 0 } ``` # 编辑距离 这道题有三种操作，增删改，我们定义 dp[i][j] 是 word1[0..i-1] 到 word2[0..j-1] 所需要的最少编辑。 那么来到 dp[i][j] * 删除就是 word1 少一个 → dp[i-1][j] + 1 * 插入就是 word2 少一个 → dp[i][j-1] + 1 * 替换就是 对不上就换 → dp[i-1][j-1] + 1 * 对得上就 原样搬 → dp[i-1][j-1] 所以得出如下代码 ```go func minDistance(word1 string, word2 string) int { n, m := len(word1), len(word2) dp := make([][]int, n+1) for i := range dp { dp[i] = make([]int, m+1) } for i := 0; i <= n; i++ { dp[i][0] = i } for j := 0; j <= m; j++ { dp[0][j] = j } for i := 1; i <= n; i++ { for j := 1; j <= m; j++ { if word1[i-1] == word2[j-1] { dp[i][j] = dp[i-1][j-1] } else { del := dp[i-1][j] + 1 add := dp[i][j-1] + 1 rep := dp[i-1][j-1] + 1 dp[i][j] = min3(del, add, rep) } } } return dp[n][m] } func min3(a, b, c int) int { return min(a, min(b, c)) } ``` # 打家劫舍II 这道题是打家劫舍的变种，实际上也就是把原本的条件加了一个首尾相连，选了第一个就不能选最后一个，选了最后一个就不能选第一个，所以进行两次分别的运算即可。 ```go func rob(nums []int) int { n := len(nums) if n == 1 { return nums[0] } r1 := robRange(nums, 0, n-2) r2 := robRange(nums, 1, n-1) return max(r1, r2) } func robRange(nums []int, l, r int) int { prev1, prev2 := 0, 0 for i := l; i <= r; i++ { cur := max(prev1, prev2 + nums[i]) prev2 = prev1 prev1 = cur } return prev1 } ``` # 零钱兑换 这个题目一开始还以为可以用贪心，后来发现如果硬币是 [1，3，4]，amount=6，最少硬币是2，而贪心会得到3，所以不能用贪心，只能用动态规划了，定义 dp[i] 是凑够 i 金额用的最少硬币数，那么有公式如下： $ dp[i] = min(dp[i], dp[i-c] + 1) $ 那么有初始状态 dp[0] = 0，dp[1..amount]=amount+1（不可能的值） ```go func coinChange(coins []int, amount int) int { dp := make([]int, amount+1) for i := range dp { dp[i] = amount+1 } dp[0] = 0 for i := 1; i <= amount; i++ { for _, c := range coins { if i >= c { dp[i] = min(dp[i], dp[i - c] + 1) } } } if dp[amount] == amount+1 { return -1 } return dp[amount] } ``` Last modification：July 20, 2025 © Allow specification reprint Support Appreciate the author AliPayWeChat Like 如果觉得我的文章对你有用，请随意赞赏
