今天是我们讲解「动态规划专题」中的「背包问题」的第十九篇。
今天将学习「背包问题求方案数」问题。
另外,我在文章结尾处列举了我所整理的关于背包问题的相关题目。
背包问题我会按照编排好的顺序进行讲解(每隔几天更新一篇,确保大家消化)。
你可以先尝试做做,也欢迎你向我留言补充,你觉得与背包相关的 DP 类型题目 ~
这是 LeetCode 上的「494. 目标和」,难度为「中等」。
Tag : 「DFS」、「记忆化搜索」、「背包 DP」、「01 背包」
给你一个整数数组 nums 和一个整数 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
提示:
数据范围只有
,而且每个数据只有
两种选择,因此可以直接使用 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]);
}
}
不难发现,在 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);
}
}
能够以「递归」的形式实现动态规划(记忆化搜索),自然也能使用「递推」的方式进行实现。
根据记忆化搜索的分析,我们可以定义:
代表考虑前
个数,当前计算结果为
的方案数,令 nums
下标从
开始。
那么
为最终答案,
为初始条件:代表不考虑任何数,凑出计算结果为
的方案数为
种。
根据每个数值只能搭配
使用,可得状态转移方程:
到这里,既有了「状态定义」和「转移方程」,又有了可以滚动下去的「有效值」(起始条件)。
距离我们完成所有分析还差最后一步。
当使用递推形式时,我们通常会使用「静态数组」来存储动规值,因此还需要考虑维度范围的:
nums
数组长度s
为所有 nums
元素的总和(题目给定了 nums[i]
为非负数的条件,否则需要对 nums[i]
取绝对值再累加),那么中间结果的范围为因此,我们可以确定动规数组的大小。同时在转移时,对第二维度的使用做一个 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];
}
}
在上述「动态规划」分析中,我们总是尝试将所有的状态值都计算出来,当中包含很多对「目标状态」不可达的“额外”状态值。
即达成某些状态后,不可能再回到我们的「目标状态」。
例如当我们的
不为
和
时,
和
就是两个对「目标状态」不可达的“额外”状态值,到达
或
已经使用所有数值,对
不可达。
那么我们如何规避掉这些“额外”状态值呢?
我们可以从哪些数值使用哪种符号来分析,即划分为「负值部分」&「非负值部分」,令「负值部分」的绝对值总和为
,即可得:
变形得:
问题转换为:只使用
运算符,从 nums
凑出
的方案数。
这样「原问题的具体方案」和「转换问题的具体方案」具有一一对应关系:「转换问题」中凑出来的数值部分在实际计算中应用
,剩余部分应用
,从而实现凑出来原问题的
值。
另外,由于 nums
均为非负整数,因此我们需要确保
能够被
整除。
同时,由于问题转换为 从 nums
中凑出
的方案数,因此「状态定义」和「状态转移」都需要进行调整(01 背包求方案数):
定义
为从 nums
凑出总和「恰好」为
的方案数。
最终答案为
,
为起始条件:代表不考虑任何数,凑出计算结果为
的方案数为
种。
每个数值有「选」和「不选」两种决策,转移方程为:
代码:
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];
}
}