DP

70.爬楼梯 1 2 3 4 5 6 7 8 9 10 func climbStairs(n int) int { cache := make([]int, n+1) cache[0], cache[1] = 1, 1 for i := 2; i <= n; i++ { cache[i] = cache[i-1] + cache[i-2] } return cache[n] } 最简单的一维 DP 题，遇见属于白给，最标准的没有套路的 DP，完全不需要解释。 198.打家劫舍 1 2 3 4 5 6 7 8 9 10 func rob(nums []int) int { cache := make([]int, len(nums)+1) cache[0], cache[1] = 0, nums[0] for i := 2; i <= len(nums); i++ { cache[i] = max(nums[i-1]+cache[i-2], cache[i-1]) } return cache[len(nums)] } 经典打家劫舍，难度同样属于白给。...

动态规划经典问题学习记录 0-1 背包 问题描述 有 $n$ 个物品，第 $i$ 个物品的体积为 $w[i]$ ，价值为 $v[i]$ ，每个物品最多选一次，求体积和不超过 $capacity$ 时的最大价值和。 通过回溯去思考解题思路 先去思考当前的操作，即枚举第 $i$ 个物品选与不选： 不选，剩余容量不变。 选，剩余容量减少 $w[i]$ 。 递归到子问题，在剩余容量为 $c$ 时，从前 $i$ 个物品中得到的最大价值和。 下一个递归子问题： 不选，在剩余容量为 $c$ 时，从前 $i-1$ 个物品中得到的最大价值和。 选，在剩余容量为 $c-w[i]$ 时，从前 $i-1$ 个物品中得到的最大价值和。 最终得到的递归公式：$dfs(i,c) = max(dfs(i-1, c),dfs(i-1, c-w[i])+v[i])$ 对应的代码就是： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def zero_one_backpack(capacity: int, w: List[int], v: List[int]) -> int: n = len(w) @cache # 记忆化搜索数组 def dfs(i: int, c: int) -> int: # 跳出递归条件 if i < 0: return 0 # 容量不足时 if c < w[i]: return dfs(i-1, c) # 将问题进一步分解 return max(dfs(i-1, c), dfs(i-1, c-w[i]) + v[i]) return dfs(n-1, capacity) 以上就是 0-1 背包的“至多装 capacity”的递归+记忆化搜索形式，其实也可以写成递推式：$dp[i][c] = max(dp[i-1][c],dp[i-1] [c-w[i]]+v[i])$...