背包问题具备的特征：给定一个target，target可以是数字也可以是字符串，再给定一个数组nums，nums中装的可能是数字，也可能是字符串，问：能否使用nums中的元素做各种排列组合得到target。
最大最小问题核心公式：
dp[i] = min(dp[i], dp[i-num]+1) or dp[i] = max(dp[i], dp[i-num]+1)
Tips:
- 如果是完全背包，即数组中的元素可重复使用，
nums放在外循环，target在内循环。且内循环正序。 - 如果是0-1背包，即数组中的元素不可重复使用，
nums放在外循环，target在内循环，且内循环倒序； - 如果组合问题（完全背包问题）需"考虑元素之间的顺序，需将
target放在外循环，将nums放在内循环，（如T377零钱兑换、T70爬楼梯、T139单词拆分）。
ps：不涉及顺序的完全背包问题，nums和target在内外循环都可以，但建议nums外循环，target内循环。
1.零钱兑换（322-中）
题目描述：给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
你可以认为每种硬币的数量是无限的。
示例：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
输入：coins = [2], amount = 3
输出：-1
输入：coins = [1], amount = 0
输出：0
思路：
法1：动态规划：完全背包问题。可以采用自顶向上的思路。dp[i]达到金额i需要的最少的硬币，那么转移方程为：dp[i] = min(dp[i], dp[i-num]+1) 。
法2：dfs+剪枝：本题通过逆序遍历面值数组，有点类似贪心（先找大面值硬币），因为我们要寻找最小数量的硬币。用for循环进行深度优先搜索，关键：当k + count >= ans 时，即得到的结果大于等于当前最小能达到amount的硬币数量，进行剪枝。但超时。。
代码实现：
class Solution {
// 动态规划
public int coinChange(int[] coins, int amount) {
if (coins == null || coins.length == 0) {
return 0;
}
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
// 选取使用or不使用当前硬币的最小值
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
// dfs + 剪枝：超时
private int ans = Integer.MAX_VALUE;
public int coinChange(int[] coins, int amount) {
Arrays.sort(coins);
dfs(coins, coins.length - 1, 0, amount);
return ans == Integer.MAX_VALUE ? -1 : ans;
}
// cnt：当前已经添加的硬币数量
private void dfs(int[] coins, int i, int count, int amount) {
if (amount == 0) {
ans = Math.min(ans, count);
return;
}
if (i < 0) {
return;
}
// 乘法加速:可以满足当前面值的最大数量,即从最大值开始试
int a = amount / coins[i];
for (int k = a; k >= 0 && k + count < ans; k--) {
dfs(coins, i - 1, count + k, amount - k * coins[i]);
}
}
}
2.完全平方数（279-中）
题目描述：给定正整数n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于n。你需要让组成和的完全平方数的个数最少。给你一个整数n ，返回和为 n 的完全平方数的 最少数量 。
示例：
输入：n = 13
输出：2
解释：13 = 4 + 9
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4
思路：完全背包问题。类比322零钱兑换思路。定义numsArray记录小于n的完全平方数。
代码1：动态规划
private List<Integer> nums = new ArrayList<>();
public int numSquares(int n) {
nums = numsArray(n);
int[] dp = new int[n + 1];
Arrays.fill(dp, n + 1);
dp[0] = 0; // 0不需要完全平方数
for (int num : nums) {
for (int i = 1; i <= n; ++i) {
if (i >= num) {
dp[i] = Math.min(dp[i], dp[i - num] + 1);
}
}
}
return dp[n];
}
private List<Integer> numsArray(int n) {
for (int i = 1; i * i <= n; ++i) {
nums.add(i * i);
}
return nums;
}
代码2：dfs+剪枝
private int ans = Integer.MAX_VALUE;
public int numSquares(int n) {
// 找到距离n最近（最大）的完全平方数
int num = (int)Math.sqrt(n);
int[] nums = new int[num];
for (int i = 0; i < num; ++i) {
nums[i] = (i + 1) * (i + 1);
}
dfs(nums.length - 1, nums, 0, n);
return ans == Integer.MAX_VALUE ? -1 : ans;
}
private void dfs(int i, int[] nums, int count, int n) {
if (n == 0) {
ans = Math.min(ans, count);
return;
}
if (i < 0) return;
// 乘法加速
int a = n / nums[i];
// 倒序遍历，超过当前最小值ans，剪枝
for (int k = a; k >= 0 && k + count < ans; --k) {
dfs(i - 1, nums, k + count, n - k * nums[i]);
}
}
3.一和零（474-中）
题目描述：给你一个二进制字符串数组strs 和两个整数 m和 n 。请你找出并返回strs 的最大子集的大小，该子集中 最多 有 m个 0 和 n 个 1 。注：子集包括本身。
示例：
输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
思路：本题为01背包问题，只不过有两个背包。dp[i][j]表示达到i个0和j个1的最大子集的大小。注：在进入循环之前，我们要先计算每个字符串中0和1的个数。通过逆序嵌套完成两个背包的目标值求解!
代码1：动态规划
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp = new int[m + 1][n + 1];
// 01背包：每个字符串只使用一次
for (String s : strs) {
// 计算0和1的数量
int zeros = 0, ones = 0;
for (char ch : s.toCharArray()) {
if (ch == '0') zeros++;
else ones++;
}
for (int i = m; i >= zeros; --i) {
for (int j = n; j >= ones; --j) {
// dp[i][j]表示到达i和j的子集数量
dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
}
}
}
return dp[m][n];
}
