背包问题具备的特征：给定一个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]; }
