提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

【动态规划/背包问题】01 背包求方案数

规划 问题 方案 动态 01 背包
2023-06-13 09:15:16 时间

前言

今天是我们讲解「动态规划专题」中的「背包问题」的第十九篇。

今天将学习「背包问题求方案数」问题。

另外，我在文章结尾处列举了我所整理的关于背包问题的相关题目。

背包问题我会按照编排好的顺序进行讲解（每隔几天更新一篇，确保大家消化）。

你可以先尝试做做，也欢迎你向我留言补充，你觉得与背包相关的 DP 类型题目 ~

题目描述

这是 LeetCode 上的「494. 目标和」，难度为「中等」。

Tag : 「DFS」、「记忆化搜索」、「背包 DP」、「01 背包」

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

  • 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 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
+1 + 1 + 1 + 1 - 1 = 3

示例 2：

输入：nums = [1], target = 1
输出：1

提示：

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums[i]) <= 100
  • -1000 <= target <= 100

DFS

数据范围只有

20

，而且每个数据只有

+/-

两种选择，因此可以直接使用 DFS 进行「爆搜」。

而 DFS 有「使用全局变量维护」和「接收返回值处理」两种形式。

代码：

class Solution {
    public int findTargetSumWays(int[] nums, int t) {
        return dfs(nums, t, 0, 0);
    }
    int dfs(int[] nums, int t, int u, int cur) {
        if (u == nums.length) {
            return cur == t ? 1 : 0;
        }
        int left = dfs(nums, t, u + 1, cur + nums[u]);
        int right = dfs(nums, t, u + 1, cur - nums[u]);
        return left + right;
    }
}

class Solution {
    int ans = 0;
    public int findTargetSumWays(int[] nums, int t) {
        dfs(nums, t, 0, 0);
        return ans;
    }
    void dfs(int[] nums, int t, int u, int cur) {
        if (u == nums.length) {
            ans += cur == t ? 1 : 0;
            return;
        }
        dfs(nums, t, u + 1, cur + nums[u]);
        dfs(nums, t, u + 1, cur - nums[u]);
    }
}
  • 时间复杂度：
O(2^n)
  • 空间复杂度：忽略递归带来的额外空间消耗。复杂度为
O(1)

记忆化搜索

不难发现，在 DFS 的函数签名中只有「数值下标 u」和「当前结算结果 cur」为可变参数，考虑将其作为记忆化容器的两个维度，返回值作为记忆化容器的记录值。

由于 cur 存在负权值，为了方便，我们这里不设计成静态数组，而是使用「哈希表」进行记录。

代码：

class Solution {
    public int findTargetSumWays(int[] nums, int t) {
        return dfs(nums, t, 0, 0);
    }
    Map<String, Integer> cache = new HashMap<>();
    int dfs(int[] nums, int t, int u, int cur) {
        String key = u + "_" + cur;
        if (cache.containsKey(key)) return cache.get(key);
        if (u == nums.length) {
            cache.put(key, cur == t ? 1 : 0);
            return cache.get(key);
        }
        int left = dfs(nums, t, u + 1, cur + nums[u]);
        int right = dfs(nums, t, u + 1, cur - nums[u]);
        cache.put(key, left + right);
        return cache.get(key);
    }
}
  • 时间复杂度：
O(n * \sum_{i = 0}^{n - 1} abs(nums[i]))
  • 空间复杂度：忽略递归带来的额外空间消耗。复杂度为
O(n * \sum_{i = 0}^{n - 1} abs(nums[i]))

动态规划

能够以「递归」的形式实现动态规划（记忆化搜索），自然也能使用「递推」的方式进行实现。

根据记忆化搜索的分析，我们可以定义：

f[i][j]

代表考虑前

i

个数，当前计算结果为

j

的方案数，令 nums 下标从

1

开始。

那么

f[n][target]

为最终答案，

f[0][0] = 1

为初始条件：代表不考虑任何数，凑出计算结果为

0

的方案数为

1

种。

根据每个数值只能搭配

+/-

使用，可得状态转移方程：

f[i][j] = f[i - 1][j - nums[i - 1]] + f[i - 1][j + nums[i - 1]]

到这里，既有了「状态定义」和「转移方程」，又有了可以滚动下去的「有效值」（起始条件）。

距离我们完成所有分析还差最后一步。

当使用递推形式时，我们通常会使用「静态数组」来存储动规值，因此还需要考虑维度范围的：

  • 第一维为物品数量：范围为 nums 数组长度
  • 第二维为中间结果：令 s 为所有 nums 元素的总和（题目给定了 nums[i] 为非负数的条件，否则需要对 nums[i] 取绝对值再累加），那么中间结果的范围为
[-s, s]

因此，我们可以确定动规数组的大小。同时在转移时，对第二维度的使用做一个 s 的右偏移，以确保「负权值」也能够被合理计算/存储。

代码：

class Solution {
    public int findTargetSumWays(int[] nums, int t) {
        int n = nums.length;
        int s = 0;
        for (int i : nums) s += Math.abs(i);
        if (Math.abs(t) > s) return 0;
        int[][] f = new int[n + 1][2 * s + 1];
        f[0][0 + s] = 1;
        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            for (int j = -s; j <= s; j++) {
                if ((j - x) + s >= 0) f[i][j + s] += f[i - 1][(j - x) + s];
                if ((j + x) + s <= 2 * s) f[i][j + s] += f[i - 1][(j + x) + s];
            }
        }
        return f[n][t + s];
    }
}
  • 时间复杂度：
O(n * \sum_{i = 0}^{n - 1} abs(nums[i]))
  • 空间复杂度：
O(n * \sum_{i = 0}^{n - 1} abs(nums[i]))

动态规划（优化）

在上述「动态规划」分析中，我们总是尝试将所有的状态值都计算出来，当中包含很多对「目标状态」不可达的“额外”状态值。

即达成某些状态后，不可能再回到我们的「目标状态」。

例如当我们的

target

不为

-s

和

s

时，

-s

和

s

就是两个对「目标状态」不可达的“额外”状态值，到达

-s

或

s

已经使用所有数值，对

target

不可达。

那么我们如何规避掉这些“额外”状态值呢？

我们可以从哪些数值使用哪种符号来分析，即划分为「负值部分」&「非负值部分」，令「负值部分」的绝对值总和为

m

，即可得：

(s - m) - m = s - 2 * m = target

变形得：

m = \frac{s - target}{2}

问题转换为：只使用

+

运算符，从 nums 凑出

m

的方案数。

这样「原问题的具体方案」和「转换问题的具体方案」具有一一对应关系：「转换问题」中凑出来的数值部分在实际计算中应用

-

，剩余部分应用

+

，从而实现凑出来原问题的

target

值。

另外，由于 nums 均为非负整数，因此我们需要确保

s - target

能够被

2

整除。

同时，由于问题转换为 从 nums 中凑出

m

的方案数，因此「状态定义」和「状态转移」都需要进行调整（01 背包求方案数）：

定义

f[i][j]

为从 nums 凑出总和「恰好」为

j

的方案数。

最终答案为

f[n][m]

，

f[0][0] = 1

为起始条件：代表不考虑任何数，凑出计算结果为

0

的方案数为

1

种。

每个数值有「选」和「不选」两种决策，转移方程为：

f[i][j] = f[i - 1][j] + f[i - 1][j - nums[i - 1]]

代码：

class Solution {
    public int findTargetSumWays(int[] nums, int t) {
        int n = nums.length;
        int s = 0;
        for (int i : nums) s += Math.abs(i);
        if (t > s || (s - t) % 2 != 0) return 0;
        int m = (s - t) / 2;
        int[][] f = new int[n + 1][m + 1];
        f[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            for (int j = 0; j <= m; j++) {
                f[i][j] += f[i - 1][j];
                if (j >= x) f[i][j] += f[i - 1][j - x];
            }
        }
        return f[n][m];
    }
}
  • 时间复杂度：
O(n * (\sum_{i = 0}^{n - 1} abs(nums[i]) - target))
  • 空间复杂度：
O(n * (\sum_{i = 0}^{n - 1} abs(nums[i]) - target))

背包问题（目录）

  1. 01背包 : 背包问题 第一讲
    1. 【练习】01背包 : 背包问题 第二讲
    2. 【学习&练习】01背包 : 背包问题 第三讲
  2. 完全背包 : 背包问题 第四讲
    1. 【练习】完全背包 : 背包问题 第五讲
    2. 【练习】完全背包 : 背包问题 第六讲
    3. 【练习】完全背包 : 背包问题 第七讲
  3. 多重背包 : 背包问题 第八讲
  4. 多重背包（优化篇）
    1. 【上】多重背包（优化篇）: 背包问题 第九讲
    2. 【下】多重背包（优化篇）: 背包问题 第十讲
  5. 混合背包 : 背包问题 第十一讲
  6. 分组背包 : 背包问题 第十二讲
    1. 【练习】分组背包 : 背包问题 第十三讲
  7. 多维背包
    1. 【练习】多维背包 : 背包问题 第十四讲
    2. 【练习】多维背包 : 背包问题 第十五讲
  8. 树形背包 : 背包问题 第十六讲
    1. 【练习篇】树形背包 : 背包问题 第十七讲
    2. 【练习篇】树形背包 : 背包问题 第十八讲
  9. 背包求方案数
    1. 【练习】背包求方案数 : 本篇
    2. 【练习】背包求方案数
  10. 背包求具体方案
    1. 【练习】背包求具体方案
  11. 泛化背包
    1. 【练习】泛化背包

相关文章