01背包类算法题

关于背包问题的概念可以参考此处

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];
    }