关于背包问题的概念可以参考此处
leetcode 416. 分割等和子集
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
示例 1: 输入: [1, 5, 11, 5]，输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
示例 2:输入: [1, 2, 3, 5]，输出: false
其实可以看成是一个01背包问题。能不能装满sum/2,能的话就返回true，否则返回false。
public boolean canPartition(int[] nums) {
if (nums == null || nums.length == 0) {
return false;
}
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 != 0) {
return false;
}
sum = sum / 2;
boolean[] res = new boolean[sum + 1];
res[0] = true;
for (int num : nums) {
for (int i = sum; i >= num; i--) {
res[i] = res[i] || res[i - num];
}
}
return res[sum];
}leetcode 322. 零钱兑换
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1
示例 2: 输入: coins = [2], amount = 3 输出: -1
说明:你可以认为每种硬币的数量是无限的。
可以看成是一个完全背包问题。用一个完全背包装满指定的金额
public int coinChange(int[] coins, int amount) {
if (coins == null || coins.length == 0 || amount == 0) {
return 0;
}
int[] dp = new int[amount + 1];
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
//如果需要组成的金额正好和某个硬币的面额相等
if (coin == i) {
dp[i] = 1;
} else {
//只有能凑成dp[i - coin]才能凑成dp[i]
if (dp[i - coin] != 0) {
if (dp[i] == 0) {
//暂时能凑成dp[i-coin]，但是凑不成dp[i]，那么直接将dp[i-coin]+1
dp[i] = dp[i - coin] + 1;
} else {
//既能凑成dp[i-coin]，又能凑不成dp[i]，那么取dp[i-coin]+1和dp[i]的较小值
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
}
}
}
return dp[amount] == 0 ? -1 : dp[amount];
}leetcode 518. 零钱兑换 II
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1: 输入: amount = 5, coins = [1, 2, 5] 输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2: 输入: amount = 3, coins = [2] 输出: 0
解释: 只用面额2的硬币不能凑成总金额3。
因为每种面额是无限的，因此也是一个完全背包问题。
d 为动态规划记录数组:
d[i] 代表，最多 i 元钱时可兑换的分配方案数量;
d[0] 时为初始条件，表示0元可以用0元兑换1次，所以 d[0] = 1。
d[i - c] 中，c 代表当前面值，d[i - c] 表示 i - c 元钱所有分配方案之和，d[i] 分配方案应该等于所有 d[i - c] 分配方案之和，这样就可以快速的计算出 d[amount] 的和了。
public int change(int amount, int[] coins) {
if (coins == null) {
return 0;
}
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
dp[i] += dp[i - coin];
}
}
return dp[amount];
}leetcode 139. 单词拆分
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
示例 1：输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。
示例 2：输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
注意你可以重复使用字典中的单词。
示例 3：输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
因为可以重复使用，所以这是一个经典的完全背包问题，dp[i]表示从0到i能否拆分。
状态转移方程为：dp[i] = s[j-->i] in wordDict and dp[j]。
注意 ：需要定义dp[0]为 true，因为如果字符串本身就在 wordDict 中，就不必看 dp 了，可以直接判断为 true，因此 dp[0] = true；
public boolean wordBreak(String s, List<String> wordDict) {
if (s == null) {
return true;
}
if (wordDict == null || wordDict.size() == 0) {
return false;
}
Set<String> set = new HashSet<>(wordDict);
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && set.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}leetcode 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。
此题的状态转移方程为dp[i] = dp[i-nums[0]]+dp[i-nums[1]]+...dp[i-nums[len-1]],条件为i>=nums[j];
dp[0] = 1,dp[0]表示组成0，一个数都不选就可以了，所以dp[0]=1
举个例子。假设nums={1,2,3}; target = 4
dp[4] = dp[4-1]+dp[4-2]+dp[4-3] = dp[3]+dp[2]+dp[1]
dp[1] = dp[0] = 1;
dp[2] = dp[1]+dp[0] = 2;
dp[3] = dp[2]+dp[1]+dp[0] = 4;
dp[4] = dp[4-1]+dp[4-2]+dp[4-3] = dp[3]+dp[2]+dp[1] = 7
代码如下
public int combinationSum4(int[] nums, int target) {
if (nums == null) {
return 0;
}
int[] dp = new int[target + 1];
//dp[0]表示组成0，一个数都不选就可以了，所以dp[0]=1
dp[0] = 1;
for (int i = 1; i <= target; i++) {
for (int num : nums) {
if (i >= num) {
dp[i] += dp[i - num];
}
}
}
return dp[target];
}