算法分析课程博客分享 8

发表于 | 分类于

算法分析课程博客分享 8

322. 零钱兑换(Coin Change)

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1

示例 2:
输入: coins = [2], amount = 3
输出: -1

说明:

  • 你可以认为每种硬币的数量是无限的。

解题思路:
这是一道完全背包问题的推广题，观察题目，我们可以将总金额 amount 视为背包的容量，coins 视为不同的物品，而每件物品的价值皆为 1。在这个视角下，我们将问题转换为求往容量为 c 的背包中放满物品时，背包的最小价值。因此，动态规划的转换函数为：

  • c < coins[n]: dp[n][c] = dp[n-1][c]
  • c >= coins[n]: dp[n][c] = min(dp[n-1][c], dp[n][c-coins[n]]+1)

首先，我们对 dp 矩阵进行初始化，我们将矩阵的所有位置都初始化为 amount+1，表示无法将背包放满。注意，因为硬币的体积至少为 1，所以放满一个容量为 amount 的背包至多需要 amount+1 个硬币。接下来，我们需要对 coins[0] 进行特殊处理，显然，只使用 coins[0] 来填充背包的话，当且仅当 c % coins[0] == 0 时能放满的，而此时放满所需的硬币数目为 c / coins[0]。当然，我们也可以用状态转移方程来对 coins[0] 进行处理，此时替换的代码如下： 

dp[0][0] = 0;
for (int c = 0; c <= amount; ++c) {
    if (c >= coins[0]) {
        dp[0][c] = min(dp[0][c], dp[0][c-coins[0]]+1);
    }
}


之后，我们就只需解决一个经典的完全背包问题，具体代码如下： 

int coinChange(vector<int>& coins, int amount) {
    vector<vector<int>> dp(coins.size(), vector<int>(amount+1, amount+1));
    for (int c = 0; c <= amount; ++c) {
        if (c % coins[0] == 0) {
            dp[0][c] = c / coins[0];
        }
    }
    for (int n = 1; n < coins.size(); ++n) {
        for (int c = 0; c <= amount; ++c) {
            if (c < coins[n]) {
                dp[n][c] = dp[n-1][c];
            } else {
                dp[n][c] = min(dp[n-1][c], dp[n][c-coins[n]]+1);
            }
        }
    }

    int count = dp[coins.size()-1][amount];
    return (count == amount+1) ? (-1) : (count);
}


其实，我们也可以发现，题目并不要求我们保留硬币的选取方案，故我们可以改用一个一维数组来进行动态规划，从而优化程序的复杂度。具体代码如下： 

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount+1, amount+1);
    dp[0] = 0;
    for (int n = 0; n < coins.size(); ++n) {
        for (int c = 1; c <= amount; ++c) {
            if (c >= coins[n]) {
                dp[c] = min(dp[c], dp[c-coins[n]]+1);
            }
        }
    }

    return (dp[amount] == amount+1) ? (-1) : (dp[amount]);
}


518. 零钱兑换 II(Coin Change 2)

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

注意: 你可以假设

  • 0 <= amount (总金额) <= 5000
  • 1 <= coin (硬币面额) <= 5000
  • 硬币种类不超过500种
  • 结果符合32位符号整数

示例 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。

示例 3:
输入: amount = 10, coins = [10]
输出: 1

解题思路:
与上一题一样，属于动态规划的题目，先假设我们知道使用前 n-1 种硬币放满容量小于等于 c 的背包的不同组合数，当我们拿到第 n 种硬币时，若 c >= coins[n]，则使用前 n 种硬币放满容量为 c 的背包的不同组合数为：使用前 n-1 种硬币放满容量为 c 的背包的不同组合数加上使用前 n 种硬币放满容量为 c-coins[n] 的背包的不同组合数。因此，我们可以写出状态转移方程：

  • c < coins[n]: dp[n][c] = dp[n-1][c]
  • c >= coins[n]: dp[n][c] = dp[n-1][c] + dp[n][c-coins[n]]

而最终，我们要求解的答案实际是 dp[n][amount]，考虑到我们不需要记录硬币的组合形式，我们可以只使用一个一维数组来进行动态规划，具体代码如下： 

int change(int amount, vector<int>& coins) {
    vector<int> dp(amount+1, 0);
    dp[0] = 1;
    for (int n = 0; n < coins.size(); ++n) {
        for (int c = 1; c <= amount; ++c) {
            if (c >= coins[n]) {
                dp[c] += dp[c-coins[n]];
            }
        }
    }
    return dp[amount];
}


416. 分割等和子集(Partition Equal Subset Sum)

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意:

  • 每个数组中的元素不会超过 100
  • 数组的大小不会超过 200

示例 1:
输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:
输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.

解题思路:
这道题可以用和 零钱兑换 II 类似的思想来解决。我们要将给出的数组等分成两份，则每一份的和为总和的一半，如果总和不能被 2 整除，那么我们肯定无法将当前数组等分。考虑到我们只需将数组分成两份，所以实际上，我们只需找出一个和为 sum/2 的子数组，而剩下的元素自然会组成另一个和为 sum/2 的子数组。我们将 sum/2 视作背包的容量，nums 视作物品，那么我们就可以将问题转化为确认是否存在填满背包的组合，至于有多少种不同组合数，我们是不需要关注的。这道题是一个 0-1 背包问题，而不是完全背包问题。因此，我们需要稍微修改一下状态转移方程：

  • c < nums[n]: dp[n][c] = dp[n-1][c]
  • c >= nums[n]: dp[n][c] = dp[n-1][c] + dp[n-1][c-nums[n]]

显然，我们也可以用一个一维数组来实现动态规划，由于我们的转移方程需要用到 dp[n-1][c-nums[n]] 的值，我们在内循环需要从后往前遍历，防止 dp[n-1][c-nums[n]] 的值被修改为 dp[n][c-nums[n]] 的值，具体代码如下： 

bool canPartition(vector<int>& nums) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum % 2 != 0)
        return false;
    sum /= 2;

    vector<int> dp(sum+1, 0);
    dp[0] = 1;
    for (int n = 0; n < nums.size(); ++n) {
        for (int c = sum; c > 0; --c) {
            if (c >= nums[n]) {
                dp[c] += dp[c-nums[n]];
            }
        }
    }

    return dp[sum] != 0;
}


我们还可以进一步优化代码的效率，对于上面的代码，当 c < nums[n] 时，dp[c] 的值是不需要更新的，所以我们无需遍历 (1, nums[n]) 范围的元素。且外，我们也不关注究竟有多少种组合数，我们可以使用 char 数组来进行动态规划（因为 vector<bool> 需要类型转换，所以速度会变慢），具体代码如下： 

bool canPartition(vector<int>& nums) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum & 1 != 0)
        return false;
    sum >>= 1;

    vector<char> dp(sum+1, 0);
    dp[0] = 1;
    for (int n : nums) {
        for (int c = sum; c >= n; --c) {
            dp[c] |= dp[c-n];
        }
    }

    return dp[sum];
}