星尘

动态规划总结-背包问题

发表于 更新于 分类于 ，

基础

斐波那契数

斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给你n ，请计算 F(n) 。

  1. dp[i]的定义为：第i个数的斐波那契数值是dp[i]
  2. 状态转移方程 dp[i] = dp[i - 1] + dp[i - 2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def fib(self, n: int) -> int:
       
        # 排除 Corner Case
        if n == 0:
            return 0
        
        # 创建 dp table 
        dp = [0] * (n + 1)

        # 初始化 dp 数组
        dp[0] = 0
        dp[1] = 1

        # 遍历顺序: 由前向后。因为后面要用到前面的状态
        for i in range(2, n + 1):

            # 确定递归公式/状态转移公式
            dp[i] = dp[i - 1] + dp[i - 2]
        
        # 返回答案
        return dp[n]

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。

  1. dp[i]： 爬到第i层楼梯，有dp[i]种方法

  2. 首先是dp[i - 1]，上i-1层楼梯，有dp[i - 1]种方法，那么再一步跳一个台阶不就是dp[i]了么。

    还有就是dp[i - 2]，上i-2层楼梯，有dp[i - 2]种方法，那么再一步跳两个台阶不就是dp[i]了么。

    那么dp[i]就是 dp[i - 1]与dp[i - 2]之和！所以dp[i] = dp[i - 1] + dp[i - 2] 。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 1:
            return n
        
        dp = [0] * (n + 1)
        dp[1] = 1
        dp[2] = 2
        
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        
        return dp[n]

使用最小花费爬楼梯

数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。

示例 ：

  • 输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
  • 输出：6
  • 解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。

  1. dp[i]的定义：到达第i台阶所花费的最少体力为dp[i]

  2. 可以有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2]。

    dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。

    dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。

    那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢？一定是选最小的，所以dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        dp = [0] * (len(cost) + 1)
        dp[0] = 0  # 初始值，表示从起点开始不需要花费体力
        dp[1] = 0  # 初始值，表示经过第一步不需要花费体力
        
        for i in range(2, len(cost) + 1):
            # 在第i步，可以选择从前一步（i-1）花费体力到达当前步，或者从前两步（i-2）花费体力到达当前步
            # 选择其中花费体力较小的路径，加上当前步的花费，更新dp数组
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])
        
        return dp[len(cost)]  # 返回到达楼顶的最小花费

不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？

  1. dp [i][j] ：表示从（0 ，0）出发，到(i, j) 有 dp [i][j] 条不同的路径。

  2. 想要求dp [i][j]，只能有两个方向来推导出来，即dp [i-1][j] 和 dp [i][j-1]。

    此时在回顾一下 dp[i - 1][j] 表示啥，是从(0, 0)的位置到(i - 1, j)有几条路径，dp[i][j - 1]同理。

    那么很自然，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因为dp[i][j]只有这两个方向过来。

  3. 首先dp[i][0]一定都是1，因为从(0, 0)的位置到(i, 0)的路径只有一条，那么dp[0][j]也同理

  4. dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，dp[i][j]都是从其上方和左方推导而来，那么从左到右一层一层遍历就可以了。

    这样就可以保证推导dp[i][j]的时候，dp[i - 1][j] 和 dp[i][j - 1]一定是有数值的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 创建一个二维列表用于存储唯一路径数
        dp = [[0] * n for _ in range(m)]
        
        # 设置第一行和第一列的基本情况
        for i in range(m):
            dp[i][0] = 1
        for j in range(n):
            dp[0][j] = 1
        
        # 计算每个单元格的唯一路径数
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        
        # 返回右下角单元格的唯一路径数
        return dp[m - 1][n - 1]

不同路径 II

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

  1. dp[i][j] ：表示从（0 ，0）出发，到(i, j) 有dp[i][j]条不同的路径。

  2. 递推公式和 不同路径 一样，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]。

    但这里需要注意一点，因为有了障碍，(i, j)如果就是障碍的话应该就保持初始状态（初始状态为0）

  3. 初始化的时候，如果(i, 0) 这条边有了障碍之后，障碍之后（包括障碍）都是走不到的位置了，所以障碍之后的dp[i][0]应该还是初始值0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid):
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        if obstacleGrid[m - 1][n - 1] == 1 or obstacleGrid[0][0] == 1:
            return 0
        dp = [[0] * n for _ in range(m)]
        for i in range(m):
            if obstacleGrid[i][0] == 0:  # 遇到障碍物时，直接退出循环，后面默认都是0
                dp[i][0] = 1
            else:
                break
        for j in range(n):
            if obstacleGrid[0][j] == 0:
                dp[0][j] = 1
            else:
                break
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:
                    continue
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[m - 1][n - 1]

整数拆分

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

示例: 输入: 10, 输出: 36, 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

  1. dp[i]：分拆数字i，可以得到的最大乘积为dp[i]。
  2. 有两种渠道得到dp[i], 一个是j * (i - j)直接相乘。一个是j * dp[i - j]，相当于是拆分(i - j)。也可以这么理解，j * (i - j)是单纯的把整数拆分为两个数相乘，而j * dp[i - j]是拆分成两个以及两个以上的个数相乘。所以递推公式：dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j});
  3. 那么在取最大值的时候，为什么还要比较dp[i] 呢？因为在递推公式推导的过程中，每次计算dp[i]，取最大的而已。
  4. dp[i] 是依靠 dp[i - j]的状态，所以遍历i一定是从前向后遍历，先有dp[i - j]再有dp[i]
  5. 因为拆分一个数n 使之乘积最大，那么一定是拆分成m个近似相同的子数相乘才是最大的。例如 6 拆成 3 * 3， 10 拆成 3 * 3 * 4。 100的话 也是拆成m个近似数组的子数 相乘才是最大的。只不过我们不知道m究竟是多少而已，但可以明确的是m一定大于等于2，既然m大于等于2，也就是 最差也应该是拆成两个相同的 可能是最大值。那么 j 遍历，只需要遍历到 n/2 就可以，后面就没有必要遍历了，一定不是最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    # 假设对正整数 i 拆分出的第一个正整数是 j（1 <= j < i），则有以下两种方案：
    # 1) 将 i 拆分成 j 和 i−j 的和，且 i−j 不再拆分成多个正整数，此时的乘积是 j * (i-j)
    # 2) 将 i 拆分成 j 和 i−j 的和，且 i−j 继续拆分成多个正整数，此时的乘积是 j * dp[i-j]
    def integerBreak(self, n):
        dp = [0] * (n + 1)   # 创建一个大小为n+1的数组来存储计算结果
        dp[2] = 1  # 初始化dp[2]为1，因为当n=2时，只有一个切割方式1+1=2，乘积为1
       
        # 从3开始计算，直到n
        for i in range(3, n + 1):
            # 遍历所有可能的切割点
            for j in range(1, i // 2 + 1):

                # 计算切割点j和剩余部分(i-j)的乘积，并与之前的结果进行比较取较大值
                
                dp[i] = max(dp[i], (i - j) * j, dp[i - j] * j)
        
        return dp[n]  # 返回最终的计算结果

不同的二叉搜索树

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

当 n 为 3 的时候：

dp[3]，就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量

元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量

元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量

元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量

有2个元素的搜索树数量就是dp[2]。

有1个元素的搜索树数量就是dp[1]。

有0个元素的搜索树数量就是dp[0]。

所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]

  1. dp[i]：1到i为节点组成的二叉搜索树的个数为dp[i]。也可以理解是i个不同元素节点组成的二叉搜索树的个数为dp[i] ，都是一样的。

  2. 在上面的分析中，其实已经看出其递推关系， dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]

    j相当于是头结点的元素，从1遍历到i为止。

    所以递推公式：dp[i] += dp[j - 1] * dp[i - j]; ，j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量

  3. dp[0] = 1 需要初始化为 1，否则乘法的结果就都变成0了。

  4. 从递归公式：dp[i] += dp[j - 1] * dp[i - j]可以看出，节点数为i的状态是依靠 i之前节点数的状态。

1
2
3
4
5
6
7
8
class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n + 1)  # 创建一个长度为n+1的数组，初始化为0
        dp[0] = 1  # 当n为0时，只有一种情况，即空树，所以dp[0] = 1
        for i in range(1, n + 1):  # 遍历从1到n的每个数字
            for j in range(1, i + 1):  # 对于每个数字i，计算以i为根节点的二叉搜索树的数量
                dp[i] += dp[j - 1] * dp[i - j]  # 利用动态规划的思想，累加左子树和右子树的组合数量
        return dp[n]  # 返回以1到n为节点的二叉搜索树的总数量

01背包

01背包

有n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。例如：

背包最大重量为4。物品为：

重量 价值
物品0 1 15
物品1 3 20
物品2 4 30

问背包能背的物品最大价值是多少？

  • dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少

  • 不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值依然和前面相同。)

  • 放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品 i 的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品 i 得到的最大价值。

  • 所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
  • 初始化的时候，第一列肯定都是0，因为背包大小为0 的时候，放不下任何物品。第一行则要根据实际情况来计算，第一行表示物品0尝试放到不同的背包中，这是如果背包可以放下，则 dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。

  • 遍历顺序：这里先遍历背包和先遍历物品都可以，可以从递推公式看出，dp[i][j] 是从上方和左上方推导出来的，所以这里的遍历顺序关系不大。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def test_2_wei_bag_problem1():
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bagweight = 4

    # 二维数组, 注意这里新增了第0列，所以 bagweight + 1
    dp = [[0] * (bagweight + 1) for _ in range(len(weight))]

    # 初始化。这里其实是 Python 特有的写法。 range(weight[0], bagweight + 1) 代表的是能放下第一个物品的背包开始。
    for j in range(weight[0], bagweight + 1):
        dp[0][j] = value[0]

    # weight数组的大小就是物品个数
    for i in range(1, len(weight)):  # 遍历物品
        for j in range(bagweight + 1):  # 遍历背包容量
            if j < weight[i]:
                dp[i][j] = dp[i - 1][j]  # 容量为 j 的背包，放不下物品i
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]) # 能放下，所以加上物品 i 的价值，value[i]

    print(dp[len(weight) - 1][bagweight])  # 取右下角的结果

test_2_wei_bag_problem1()

滚动数组（一维数组）解法

在使用二维数组的时候，递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

其实可以发现如果把dp[i - 1]那一层拷贝到dp[i]上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);

与其把dp[i - 1]这一层拷贝到dp[i]上，不如只用一个一维数组了，只用dp[j]（一维数组，也可以理解是一个滚动数组）。

  • 在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]
  • dp[j]可以通过dp[j - weight[i]]推导出来，dp[j - weight[i]] 表示容量为 dp[j - weight[i]] 的背包所背的最大价值。
  • dp[j - weight[i]] + value[i] 表示 容量为 j - 物品i重量 的背包 加上 物品i的价值。（也就是容量为j的背包，放入物品i了之后的价值即：dp[j]）。此时dp[j]有两个选择，一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]，即不放物品i，一个是取dp[j - weight[i]] + value[i]，即放物品i，指定是取最大的，毕竟是求最大价值，

  • 所以递归公式: dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

  • 遍历顺序：二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。倒序遍历是为了保证物品i只被放入一次！。但如果一旦正序遍历了，那么物品就会被重复加入多次！从后往前循环，每次取得状态不会和之前取得状态重合，这样就保证了每种物品只取了一次。

  • 两个嵌套for循环的顺序，代码中是先遍历物品嵌套遍历背包容量，不可以先遍历背包容量嵌套遍历物品。背包容量一定是要倒序遍历（原因上面已经讲了），如果遍历背包容量放在上一层，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def test_1_wei_bag_problem():
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bagWeight = 4

    # 初始化
    dp = [0] * (bagWeight + 1)
    for i in range(len(weight)):  # 遍历物品
        for j in range(bagWeight, weight[i] - 1, -1):  # 遍历背包容量，range(bagWeight, weight[i]) 表示从能放下 weight[i] 的背包开始。
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

    print(dp[bagWeight])


test_1_wei_bag_problem()

01背包两种解法的区别：

  1. 使用一维数组时，必须先遍历物品，然后遍历背包。二维数组则没有要求，可以互换。
  2. 使用一维数组时，遍历背包是倒序遍历，即从大的背包开始处理。这么做是为了保证每个物品只被放入一次（从 dp 公式可以看出，dp[j] 是从 dp[j] 之前的数推导出来的，如果是正序遍历的话，就会有值被重复计算了两次，即物品被重复放入的情况。）

分割等和子集

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。注意: 每个数组中的元素不会超过 100 数组的大小不会超过 200

示例: 输入: [1, 5, 11, 5]，输出: true，解释: 数组可以分割成 [1, 5, 5] 和 [11].

  • 这道题目是要找是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。那么只要找到集合里能够出现 sum / 2 的子集总和，就算是可以分割成两个相同元素和子集了。
  • dp[j] 表示： 容量为j的背包，所背的物品价值最大可以为dp[j]。dp[j]表示 背包总容量（所能装的总重量）是j，放进物品后，背的最大重量为dp[j]（这题中，每一个元素的数值可以看成重量也可以看成价值）
  • 01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);本题，相当于背包里放入数值，那么物品i的重量是 nums[i]，其价值也是 nums[i]。所以递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        _sum = 0

        # dp[i]中的i表示背包内总和
        # 题目中说：每个数组中的元素不会超过 100，数组的大小不会超过 200
        # 总和不会大于20000，背包最大只需要其中一半，所以10001大小就可以了
        dp = [0] * 10001
        for num in nums:
            _sum += num
        # 也可以使用内置函数一步求和
        # _sum = sum(nums)
        if _sum % 2 == 1:
            return False
        target = _sum // 2

        # 开始 0-1背包
        for num in nums:
            for j in range(target, num - 1, -1):  # 每一个元素一定是不可重复放入，所以从大到小遍历
                dp[j] = max(dp[j], dp[j - num] + num)

        # 集合中的元素正好可以凑成总和target
        if dp[target] == target:
            return True
        return False

最后一块石头的重量II

有一堆石头，每块石头的重量都是正整数。每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

如果 x == y，那么两块石头都会被完全粉碎；

如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0

示例：

  • 输入：[2,7,4,1,8,1], 输出：1

解释：

  • 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
  • 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
  • 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
  • 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

本题其实就是尽量让石头分成重量相同的两堆，相撞之后剩下的石头最小，这样就化解成01背包问题了。

  • dp[j] 表示容量（这里说容量更形象，其实就是重量）为j的背包，最多可以背最大重量为dp[j]，本题中，石头的重量是 stones[i]，石头的价值也是 stones[i] ，可以 “最多可以装的价值为 dp[j]” == “最多可以背的重量为dp[j]“
  • 递推公式 dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])
  • dp[j]中的j表示容量，那么最大容量（重量）是多少呢，就是所有石头的重量和。而我们要求的target其实只是最大重量的一半。
  • 在计算 target 的时候，target = sum / 2 因为是向下取整，所以sum - dp[target] 一定是大于等于dp[target]的。那么相撞之后剩下的最小石头重量就是 (sum - dp[target]) - dp[target]
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        dp = [0] * 15001
        total_sum = sum(stones)
        target = total_sum // 2

        for stone in stones:  # 遍历物品
            for j in range(target, stone - 1, -1):  # 遍历背包
                dp[j] = max(dp[j], dp[j - stone] + stone)

        return total_sum - dp[target] - dp[target]

目标和

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例：

  • 输入：nums: [1, 1, 1, 1, 1], S: 3，输出：5

解释：

  • -1+1+1+1+1 = 3
  • +1-1+1+1+1 = 3
  • +1+1-1+1+1 = 3
  • +1+1+1-1+1 = 3
  • +1+1+1+1-1 = 3

一共有5种方法让最终目标和为3。

  • 假设加法的总和为x，那么减法对应的总和就是sum - x。所以我们要求的是 x - (sum - x) = target，x = (target + sum) / 2 此时问题就转化为，装满容量为x的背包，有几种方法。这里的x，就是 bagSize，也就是我们后面要求的背包容量。

  • 每个物品（题目中的1）只用一次，所以是 01 背包。

  • dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法

  • 有哪些来源可以推出dp[j]呢？只要搞到nums[i]，凑成dp[j]就有dp[j - nums[i]] 种方法。

    例如：dp[j]，j 为5，

    • 已经有一个1（nums[i]） 的话，有 dp[4]种方法 凑成 容量为5的背包。
    • 已经有一个2（nums[i]） 的话，有 dp[3]种方法 凑成 容量为5的背包。
    • 已经有一个3（nums[i]） 的话，有 dp[2]中方法 凑成 容量为5的背包
    • 已经有一个4（nums[i]） 的话，有 dp[1]中方法 凑成 容量为5的背包
    • 已经有一个5 （nums[i]）的话，有 dp[0]中方法 凑成 容量为5的背包

    那么凑整dp[5]有多少方法呢，也就是把 所有的 dp[j - nums[i]] 累加起来。

  • 所以递推公式为：dp[j] += dp[j - nums[i]]

  • 目标和为0时，只有一种方案，即什么都不选, 即 dp[0] 为 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        # 计算nums的总和
        total_sum = sum(nums)  
        if abs(target) > total_sum:
          	# 此时没有方案
            return 0  
        if (target + total_sum) % 2 == 1:
          	# 此时没有方案
            return 0  
        # 目标和
        target_sum = (target + total_sum) // 2  
        # 创建动态规划数组，初始化为0
        dp = [0] * (target_sum + 1)  
        # 当目标和为0时，只有一种方案，即什么都不选
        dp[0] = 1  
        for num in nums:
            for j in range(target_sum, num - 1, -1):
                dp[j] += dp[j - num]  # 状态转移方程，累加不同选择方式的数量
        return dp[target_sum]  # 返回达到目标和的方案数

一和零

https://programmercarl.com/0474.%E4%B8%80%E5%92%8C%E9%9B%B6.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

完全背包

完全背包

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。例如，物品重量和价值如下所示：

重量 价值
物品0 1 15
物品1 3 20
物品2 4 30

每件商品都有无限个！问背包能背的物品最大价值是多少？

  • dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]

  • 我们知道01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。而完全背包的物品是可以添加多次的，所以要从小到大去遍历。

  • 01背包中二维dp数组的两个for遍历的先后循序是可以颠倒了，一维dp数组的两个for循环先后循序一定是先遍历物品，再遍历背包容量。在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的 因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。也就是说对于纯完全背包问题，其for循环的先后循环是可以颠倒的！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 方法1: 先遍历物品，再遍历背包
def test_CompletePack():
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bagWeight = 4
    dp = [0] * (bagWeight + 1)
    for i in range(len(weight)):  # 遍历物品
        for j in range(weight[i], bagWeight + 1):  # 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
    print(dp[bagWeight])
test_CompletePack()


# 方法2: 先遍历背包，再遍历物品
def test_CompletePack():
    weight = [1, 3, 4]
    value = [15, 20, 30]
    bagWeight = 4
    dp = [0] * (bagWeight + 1)
    for j in range(bagWeight + 1):  # 遍历背包容量
        for i in range(len(weight)):  # 遍历物品
            if j - weight[i] >= 0:
                dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
    print(dp[bagWeight])
test_CompletePack()

零钱兑换II

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。示例:

  • 输入: amount = 5, coins = [1, 2, 5]，输出: 4

解释: 有四种方式可以凑成总金额:

  • 5=5
  • 5=2+2+1
  • 5=2+1+1+1
  • 5=1+1+1+1+1

  • 注意本题目是求组合数，组合不强调元素之间的顺序，排列强调元素之间的顺序。5 = 2 + 2 + 1,

    5 = 2 + 1 + 2, 这表示一种组合，都是 2 2 1。但却是两种排列。

  • dp[j]：凑成总金额j的货币组合数为dp[j]

  • dp[j] 就是所有的dp[j - coins[i]]（考虑coins[i]的情况）相加。所以递推公式：dp[j] += dp[j - coins[i]]

  • dp[0] 应该为1

    对于这个递推公式 dp[j] += dp[j - coins[i]]，其中 dp[j] 表示组合凑成金额 j 的方法数。当我们考虑凑出金额为 0 的情况时，我们需要思考一下。

    如果 dp[0] 为 0，那么意味着没有任何硬币可以组合凑出金额为 0。这看起来似乎是合理的，因为我们没有任何硬币可用。然而，在动态规划中，我们需要考虑一种特殊的情况，即不使用任何硬币。当需要凑出金额为 0 时，我们实际上可以选择不使用任何硬币，这样就有一种方法可以凑出金额为 0，即空集合 {}。

    因此，为了确保我们在计算后续金额时不会漏掉这种情况，我们将 dp[0] 初始化为 1，表示存在一种方法凑出金额为 0。这样，我们的动态规划递推过程就能正确地计算出凑出其他金额的方法数。

    总结起来，将 dp[0] 初始化为 1 是为了处理金额为 0 的特殊情况，确保不会漏掉这种情况，并在后续的递推过程中得到正确的结果。– By GPT-3.5

  • 对于遍历顺序，这里因为是求组合，所以一定是 外层for循环遍历物品，内层for遍历背包。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0]*(amount + 1)
        dp[0] = 1
        # 遍历物品
        for i in range(len(coins)):
            # 遍历背包
            for j in range(coins[i], amount + 1):
                dp[j] += dp[j - coins[i]]
        return dp[amount]

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

组合总和 Ⅳ

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例: nums = [1, 2, 3]，target = 4。所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)，请注意，顺序不同的序列被视作不同的组合。因此输出为 7

  • 本题就是求排列，组合不强调顺序，排列强调顺序
  • dp[i]: 凑成目标正整数为i的排列个数为dp[i]
  • 递推公式：dp[i] += dp[i - nums[j]]
  • 同上，dp[0] 应该为1
  • 这里需要考虑顺序，所以 外层for遍历背包，内层for循环遍历物品
1
2
3
4
5
6
7
8
9
class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1
        for i in range(1, target + 1):  # 遍历背包
            for j in range(len(nums)):  # 遍历物品
                if i - nums[j] >= 0:
                    dp[i] += dp[i - nums[j]]
        return dp[target]

爬楼梯（进阶版）

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。

输入描述：输入共一行，包含两个正整数，分别表示n, m。输出描述：输出一个整数，表示爬到楼顶的方法数。

输入示例：3 2，输出示例：3。提示：当 m = 2，n = 3 时，n = 3 这表示一共有三个台阶，m = 2 代表你每次可以爬一个台阶或者两个台阶。

此时你有三种方法可以爬到楼顶。

  • 1 阶 + 1 阶 + 1 阶段
  • 1 阶 + 2 阶
  • 2 阶 + 1 阶

1阶，2阶，…. m阶就是物品，楼顶就是背包。每一阶可以重复使用，例如跳了1阶，还可以继续跳1阶。

问跳到楼顶有几种方法其实就是问装满背包有几种方法。此时大家应该发现这就是一个完全背包问题了！

  • dp[i]：爬到有i个台阶的楼顶，有dp[i]种方法
  • 求装满背包有几种方法，递推公式一般都是 dp[i] += dp[i - nums[j]]
  • 同上，dp[0] 应该为1
  • 这里对强调顺序，所以这里是求排列，所以 外层for遍历背包（楼顶），内层for循环遍历物品（1阶，2阶）

代码和上题一样。

零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。你可以认为每种硬币的数量是无限的。

示例 ：输入：coins = [1, 2, 5], amount = 11，输出：3，解释：11 = 5 + 5 + 1

  • dp[j]：凑足总额为j所需钱币的最少个数为dp[j]

  • 对于当前的金额 i，我们遍历硬币数组 coins，对于每个硬币的面额 coin，我们考虑两种情况：

    1. 如果当前的硬币面额 coin 小于等于金额 i，也就是说可以使用这个硬币来凑成金额 i。那么我们需要考虑将这个硬币放入组合中的情况。

      在这种情况下，我们需要计算凑成金额 i - coin 所需的最少硬币个数，即 dp[i - coin]。因为当前硬币 coin 的面额是已知的，所以凑成金额 i 的最少硬币个数就是凑成金额 i - coin 的最少硬币个数再加上一个硬币，所以是 dp[i - coin] + 1。

    2. 如果当前的硬币面额 coin 大于金额 i，也就是说无法使用这个硬币来凑成金额 i。那么我们不需要考虑将这个硬币放入组合中的情况，直接跳过即可。

    综上所述，我们选取两种情况中最小的硬币个数，即 min(dp[i], dp[i - coin] + 1)，作为凑成金额 i 的最少硬币个数。

  • 凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0

  • 考虑到递推公式的特性，dp[j]必须初始化为一个最大的数，否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。所以下标非0的元素都是应该是最大值。

  • 本题求钱币最小个数，那么钱币有顺序和没有顺序都可以，都不影响钱币的最小个数。所以本题并不强调集合是组合还是排列。所以顺序不重要。

  • 本题钱币数量可以无限使用，那么是完全背包。所以遍历的内循环是正序。（01背包，一维数组因为物品不能重复使用，所以内循环是倒序，且外循环遍历物品，内循环遍历背包容量）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 先遍历物品，后遍历背包
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)  # 创建动态规划数组，初始值为正无穷大
        dp[0] = 0  # 初始化背包容量为0时的最小硬币数量为0

        for coin in coins:  # 遍历硬币列表，相当于遍历物品
            for i in range(coin, amount + 1):  # 遍历背包容量
                if dp[i - coin] != float('inf'):  # 如果dp[i - coin]不是初始值，则进行状态转移
                    dp[i] = min(dp[i - coin] + 1, dp[i])  # 更新最小硬币数量

        if dp[amount] == float('inf'):  # 如果最终背包容量的最小硬币数量仍为正无穷大，表示无解
            return -1
        return dp[amount]  # 返回背包容量为amount时的最小硬币数量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 先便利背包，后遍历物品
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)  # 创建动态规划数组，初始值为正无穷大
        dp[0] = 0  # 初始化背包容量为0时的最小硬币数量为0

        for i in range(1, amount + 1):  # 遍历背包容量
            for j in range(len(coins)):  # 遍历硬币列表，相当于遍历物品
                # 如果dp[i - coins[j]]不是初始值，则进行状态转移
                if i - coins[j] >= 0 and dp[i - coins[j]] != float('inf'):  
                    dp[i] = min(dp[i - coins[j]] + 1, dp[i])  # 更新最小硬币数量

        if dp[amount] == float('inf'):  # 如果最终背包容量的最小硬币数量仍为正无穷大，表示无解
            return -1
        return dp[amount]  # 返回背包容量为amount时的最小硬币数量

完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：输入：n = 12，输出：3，解释：12 = 4 + 4 + 4

示例 2：输入：n = 13，输出：2，解释：13 = 4 + 9

  • 完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品？
  • dp[j]：和为j的完全平方数的最少数量为dp[j]
  • dp[j] 可以由dp[j - i * i]推出， dp[j - i * i] + 1 便可以凑成dp[j]。此时我们要选择最小的dp[j]，所以递推公式：dp[j] = min(dp[j - i * i] + 1, dp[j])
  • dp[0]表示 和为0的完全平方数的最小数量，那么dp[0]一定是0
  • 从递归公式 dp[j] = min(dp[j - i * i] + 1, dp[j]) 中可以看出每次dp[j]都要选最小的，所以非0下标的dp[j]一定要初始为最大值，这样dp[j]在递推的时候才不会被初始值覆盖。
  • 这里是求个数，所以有顺序和没有顺序都可以，即不管是谁在外循环，谁在内循环都可以。
1
2
3
4
5
6
7
8
9
10
11
12
# 先遍历物品, 再遍历背包
class Solution:
    def numSquares(self, n: int) -> int:
        dp = [float('inf')] * (n + 1)
        dp[0] = 0

        for i in range(1, n + 1):  # 遍历背包
            for j in range(1, int(i ** 0.5) + 1):  # 遍历物品
                # 更新凑成数字 i 所需的最少完全平方数数量
                dp[i] = min(dp[i], dp[i - j * j] + 1)

        return dp[n]
1
2
3
4
5
6
7
8
9
10
11
12
# 先遍历背包, 再遍历物品
class Solution:
    def numSquares(self, n: int) -> int:
        dp = [float('inf')] * (n + 1)
        dp[0] = 0

        for i in range(1, int(n ** 0.5) + 1):  # 遍历物品
            for j in range(i * i, n + 1):  # 遍历背包
                # 更新凑成数字 j 所需的最少完全平方数数量
                dp[j] = min(dp[j - i * i] + 1, dp[j])

        return dp[n]

在内部循环中，j 表示正在考虑的完全平方数。通过从 1 遍历到 int(i ** 0.5) + 1，代码确保了在计算 dp[i] 时只考虑了不超过 i 的完全平方数。这是因为在计算 dp[i] 时，我们只需要考虑小于等于 i 的完全平方数的情况。

例如，当 i 为 9 时，int(i ** 0.5) + 1 等于 4。因此，在内部循环中，j 的取值为 1、2、3，分别对应完全平方数 1、4、9。这样，我们只考虑了小于等于 9 的完全平方数，而不需要考虑更大的完全平方数。

通过这样的循环范围，代码能够有效地在每个 i 的情况下找到最少的完全平方数的数量，以更新 dp[i] 的值。 –By GPT3.5

单词拆分

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：拆分时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。

示例：输入: s = “applepenapple”, wordDict = [“apple”, “pen”], 输出: true，解释: 返回 true 因为 “applepenapple” 可以被拆分成 “apple pen apple”。注意你可以重复使用字典中的单词

  • 单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。

  • 拆分时可以重复使用字典中的单词，说明就是一个完全背包

  • dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。

  • 如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true

  • dp[i] 的状态依靠 dp[j] 是否为true，那么dp[0] 就是递推的根基，dp[0] 一定要为true，否则递推下去后面都都是false了

  • 下标非0的 dp[i] 初始化为 false，只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词

  • 本题其实我们求的是排列数，为什么呢。 拿 s = “applepenapple”, wordDict = [“apple”, “pen”] 举例。”apple”, “pen” 是物品，那么我们要求 物品的组合一定是 “apple” + “pen” + “apple” 才能组成 “applepenapple”。”apple” + “apple” + “pen” 或者 “pen” + “apple” + “apple” 是不可以的，那么我们就是强调物品之间顺序。所以本题一定是 先遍历 背包，再遍历物品。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        wordSet = set(wordDict)
        n = len(s)
        dp = [False] * (n + 1)  # dp[i] 表示字符串的前 i 个字符是否可以被拆分成单词
        dp[0] = True  # 初始状态，空字符串可以被拆分成单词

        for i in range(1, n + 1): # 遍历背包
            for j in range(i): # 遍历单词
              	# 如果 s[0:j] 可以被拆分成单词，并且 s[j:i] 在单词集合中存在，则 s[0:i] 可以被拆分成单词
                if dp[j] and s[j:i] in wordSet:
                    dp[i] = True  
                    break

        return dp[n]

总结

https://programmercarl.com/%E8%83%8C%E5%8C%85%E6%80%BB%E7%BB%93%E7%AF%87.html#%E6%80%BB%E7%BB%93