7.1 入门 DP

约 2713 字大约 9 分钟

2025-07-21

前言

灵神：

掌握动态规划（DP）是没有捷径的，咱们唯一能做的，就是投入时间猛猛刷题。好比学数学，只看书看视频而不做习题，是不能说学会的。

我能做的，是帮你节省找题的时间，并把这些题分类整理好。有着相同套路的题，一起做效率会更高，也更能领悟到 DP 的精髓。所以推荐按照专题刷。

题目已按照难度分排序（右侧数字为难度分）。如果遇到难度很大，题解都看不懂的题目，建议直接跳过，二刷的时候再来尝试。

记忆化搜索是新手村神器（甚至可以用到游戏后期），推荐先看动态规划入门：从记忆化搜索到递推。

但记忆化搜索并不是万能的，某些题目只有写成递推，才能结合数据结构等来优化时间复杂度，多数题目还可以优化空间复杂度。所以尽量在写完记忆化搜索后，把递推的代码也写一下。熟练之后直接写递推也可以。

7.1.1 爬楼梯

70. 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
提示
思路：dp[i] = dp[i−1] + dp[i−2]。当前台阶的方法数目等于前一层的方法数加上前两层的方法数。
```
class Solution:
def climbStairs(self, n: int) -> int:
    if n <= 2:
        return n
    f0 = 1
    f1 = 2
    while n > 2:
        f0, f1 = f1, f0 + f1
        n -= 1
    return f1
```
时间复杂度： $O(n)$ 。
空间复杂度： $O(1)$ 。
746. 使用最小花费爬楼梯
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。
示例 1：
输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
  总花费为 15 。
示例 2：
输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
  总花费为 6 。
提示
思路：dp[i] = min(dp[i−1], dp[i−2]) + cost[i]。随机选中一个位置，当前位置只有可能是：前一个台阶过来，前两个台阶过来，因此只要从中选取最小的作为上一个状态即可。注意我计算的是从 i 走的代价，如果使用dp[i] = min(dp[i−1] + cost[i-1], dp[i−2] + cost[i-2])则计算的是到 i 点的代价。
```
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
    n = len(cost)
    dp = [-1] * n
    dp[0], dp[1] = cost[0], cost[1]
    for i in range(2, n):
        dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]
    return min(dp[n - 1], dp[n - 2])
```
时间复杂度： $O(n)$ ，其中 n 为 cost 的长度。
空间复杂度： $O(n)$ 。
重要
空间优化到 $O(1)$ 。
```
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
    n = len(cost)
    f0, f1 = cost[0], cost[1]
    for i in range(2, n):
        f0, f1 = f1, min(f0, f1) + cost[i]
    return min(f0, f1)
```
时间复杂度： $O(n)$ ，其中 n 为 cost 的长度。
空间复杂度： $O(1)$ 。
377. 组合总和 Ⅳ
给你一个由不同整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。题目数据保证答案符合 32 位整数范围。
示例 1：
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
示例 2：
输入：nums = [9], target = 3
输出：0
提示
思路：本质是爬楼梯，nums 表示可以一次上几层，target 表示要到达的楼层。但这里我们不确定一次能上几层，因此要把所有可能到达这层的前置方法用 sum 求和，同时注意下标不能越界。
```
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
    dp = [1] + [0] * target
    for i in range(1, target + 1):
        dp[i] = sum(dp[i - num] for num in nums if i - num >= 0)
    return dp[-1]
```
时间复杂度： $O(target * n)$ ，其中 n 为 nums 的长度。
空间复杂度： $O(target)$ 。

7.1.2 打家劫舍

198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。
示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2：
输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示
思路：不能单纯认为只有奇数和偶数两种可能，dp[i] = max(dp[i - 2], dp[i - 3]) + nums[i]，dp[i]表示i处的最高金额，他只可能从i - 2和i - 3过来（i - 4一定会选择i - 2），最后答案一定在dp的后两个中取最大值。
```
class Solution:
def rob(self, nums: List[int]) -> int:
    n = len(nums)
    if n <= 2:
        return max(nums)
    dp = [-1] * n
    dp[0], dp[1], dp[2] = nums[0], nums[1], nums[0] + nums[2]
    for i in range(3, n):
        dp[i] = max(dp[i - 2], dp[i - 3]) + nums[i]
    return max(dp[-1], dp[-2])
```
时间复杂度： $O(n)$ ，其中 n 为 nums 的长度。
空间复杂度： $O(n)$ 。
重要
空间优化到 $O(1)$ 。
```
class Solution:
def rob(self, nums: List[int]) -> int:
    f0, f1, f2 = 0, 0, 0
    for num in nums:
        f0, f1, f2 = f1, f2, max(f0, f1) + num
    return max(f1, f2)
```
时间复杂度： $O(n)$ ，其中 n 为 nums 的长度。
空间复杂度： $O(1)$ 。
213. 打家劫舍 II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，今晚能够偷窃到的最高金额。
示例 1：
输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2：
输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 3：
输入：nums = [1,2,3]
输出：3
提示
思路：循环也就是不能同时取第一个和最后一个，那么分两种情况，要么偷第一个，那么第二个不能偷，最后一个不能偷，简化为第三个开始，倒数第二个结束的上一题子问题；不偷第一个，简化为第二个到最后一个的上一题子问题。
重要
空间优化到 $O(1)$ 。
```
class Solution:
def rob(self, nums: List[int]) -> int:
    
    def rob1(nums) -> int:
            n = len(nums)
            f0, f1, f2 = 0, 0, 0
            for num in nums:
                f0, f1, f2 = f1, f2, max(f0, f1) + num
            return max(f1, f2)

    return max(nums[0] + rob1(nums[2:-1]), rob1(nums[1:]))
```
时间复杂度： $O(n)$ ，其中 n 为 nums 的长度。
空间复杂度： $O(1)$ 。
2320. 统计放置房子的方式数
一条街道上共有 n * 2 个地块，街道的两侧各有 n 个地块。每一边的地块都按从 1 到 n 编号。每个地块上都可以放置一所房子。现要求街道同一侧不能存在两所房子相邻的情况，请你计算并返回放置房屋的方式数目。由于答案可能很大，需要对 109 + 7 取余后再返回。注意，如果一所房子放置在这条街某一侧上的第 i 个地块，不影响在另一侧的第 i 个地块放置房子。
示例 1：
输入：n = 1
输出：4
解释：
可能的放置方式：
1. 所有地块都不放置房子。
2. 一所房子放在街道的某一侧。
3. 一所房子放在街道的另一侧。
4. 放置两所房子，街道两侧各放置一所。
示例 2：
输入：n = 2
输出：9
解释：如上图所示，共有 9 种可能的放置方式。
提示
思路：由于一侧的房子不影响另一侧，因此只需算出一侧相乘即可。考虑第i处，不放房子，则dp[i] = dp[i - 1]；放房子，则dp[i] = dp[i - 2]，因此dp[i] = dp[i - 1] + dp[i - 2]。
重要
空间优化到 $O(1)$ 。
```
class Solution:
def countHousePlacements(self, n: int) -> int:
    f0, f1 = 1, 2
    while(n > 1):
        n -= 1
        f0, f1 = f1, f0 + f1
    return (f1 * f1) % (10**9 + 7)
```
时间复杂度： $O(n)$ 。
空间复杂度： $O(1)$ 。