背包问题具备的特征：给定一个target，target可以是数字也可以是字符串，再给定一个数组nums，nums中装的可能是数字，也可能是字符串，问：能否使用nums中的元素做各种排列组合得到target。
组合问题核心公式：dp[i] += dp[i - num]
Tips:
- 如果是完全背包，即数组中的元素可重复使用，
nums放在外循环，target在内循环。且内循环正序。 - 如果是0-1背包，即数组中的元素不可重复使用，
nums放在外循环，target在内循环，且内循环倒序； - 如果组合问题（完全背包问题）需考虑元素之间的顺序，需将
target放在外循环，将nums放在内循环，（如T377零钱兑换、T70爬楼梯、T139单词拆分）。
ps：不涉及顺序的完全背包问题，nums和target在内外循环都可以，但建议nums外循环，target内循环。
1.目标和 （494-中）
题目描述：给定一个非负整数数组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。
思路：
法1：dfs：使用递归，以每个位置作为起始位置，递归的终止条件是start == nums.length，检查是否为目标值，对于每一个起始位置start，都有两种状态（正或负）。
法2：动态规划：元素只能用一次，01背包问题。dp[i]表示前i个数能达到的值，对于整数i有两种状态+i 和 -i，即整个数组和划分为P(使用正号)和N(使用负号)两个部分。我们要转化为背包问题，关键是：在集合nums中找到一个和等于(S + sum(nums))/2子集，就证明存在解。
推导：
P - N = target ....1
P + N = sum(nums) ....2
带入消除N得：P = (sum(nums) + target) / 2
代码1：dfs
public int findTargetSumWays(int[] nums, int S) {
return findTargetSumWays(nums, 0, S);
}
public int findTargetSumWays(int[] nums, int start, int S) {
if (start == nums.length) {
// 终止条件
return S == 0 ? 1 : 0;
}
// 对于每个起始位置，递归的进行求解两种状态组合数
return findTargetSumWays(nums, start + 1, S - nums[start]) +
findTargetSumWays(nums, start + 1, S + nums[start]);
}
代码2：动态规划
public int findTargetSumWays(int[] nums, int S) {
int sum = sumArray(nums);
// 待寻找目标值
int W = (S + sum) / 2;
// 边界：一定不能达到目标的情况！
if (sum < S || (sum + S) % 2 == 1) {
return 0;
}
int[] dp = new int[W + 1];
dp[0] = 1;
for (int num : nums) {
for (int i = W; i >= num; --i) {
dp[i] += dp[i - num];
}
}
return dp[W];
}
private int sumArray(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
return sum;
}
2.零钱兑换II（518-中）
题目描述：给定不同面额的硬币coins 和一个总金额 amount。求解可以凑成总金额的硬币组合总数。注：每种硬币的数量是无限的。
示例：
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。
思路：完全背包问题，直接动态规划。
dp[i]：达到金额i的组合数。- 状态转移方程：
dp[i] += dp[i - coin]; - 边界条件，当
amount = 0，可达成的目标数（方案）为1，即一个也不选， 所以dp[0] = 1.
代码：动态规划
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
// 目标值为0，有一种方案：什么都不选
dp[0] = 1;
for (int coin : coins) {
for (int i = coin; i <= amount; ++i) {
//dp[i]依赖 dp[i -coin] 要先算出来，即递增for循环
dp[i] += dp[i - coin];
}
}
return dp[amount];
}
3.组合总和IV（377-中）
题目描述：给定一个由正整数组成且不存在重复数字的数组（但可以复用多次），找出和为给定目标正整数的组合的个数。请注意！顺序不同的序列被视作不同的组合。
- 进阶： 如果给定的数组中含有负数会怎么样？ 问题会产生什么变化？ 我们需要在题目中添加什么限制来允许负数的出现？
示例：
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。
思路：动态规划：本题的完全背包涉及顺序，与518.零钱兑换II不同点。其中，dp[i]代表和等于i的组合的个数。背包问题空间压缩：dp[i]依赖 dp[i - nums[j]] 要先算出来，即内层递增for循环。
代码：动态规划
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
// 这个值被其它状态参考，设置为 1 是合理的
dp[0] = 1;
for (int i = 1; i <= target; ++i) {
for (int num : nums) {
if (num <= i) {
dp[i] += dp[i - num];
}
}
}
return dp[target];
}
进阶问题：参考这里
1、如果给定的数组中含有负数会怎么样？问题会产生什么变化？
如果有负数，相当于给定数组中的元素有了更多的组合，特别是出现了一对相反数的时候，例如题目中的示例 [-4, 1, 2, 3, 4]，target = 4 的时候，-4 和 4 可以无限次地、成对添加到题目中的示例中，成为新的组合，那么这道问题就没有什么意义了。
仔细思考，负数我只要不选它就行。但由于本题的问法是“组合”，因此我们要保证有负数参与进来，不能够与已有的正数的组合之和为 0 即可。
2、我们需要在题目中添加什么限制来允许负数的出现？
- 如果有负数参与进来，不能够与已有的正数的组合之和为 0 ；
- 或者限制负数的使用次数，设计成类似 0-1 背包问题的样子。
4.爬楼梯（70-易）
题目描述：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
思路：动态规划：完全背包解法。其中：dp[i]表示到第n阶有多少种不同方法。
代码：动态规划
public int climbStairs(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
for (int j = 1; j <= n; ++j) {
for (int i = 1; i <= 2; ++i) {
if (i <= j) {
dp[j] += dp[j - i];
}
}
}
return dp[n];
}
