《剑指 Offer》专项突破版 - 面试题 101、102、103 和 104 : 和动态规划相关的背包问题（C++ 实现）

前言

面试题 101 : 分割等和子集

面试题 102 : 加减的目标值

面试题 103 : 最少的硬币数目

方法一

方法二

面试题 104 : 排列的数目

前言

背包问题是一类经典的可以应用动态规划来解决的问题。背包问题的基本描述如下：给定一组物品，每种物品都有其重量和价格，在限定的总重量内如何选择才能使物品的总价格最高。由于问题是关于如何选择最合适的物品放置于给定的背包中，因此这类问题通常被称为背包问题。

根据物品的特点，背包问题还可以进一步细分。如果每种物品只有一个，可以选择将之放入或不放入背包中，那么可以将这类问题称为 0-1 背包问题。0-1 背包问题是最基本的背包问题，其他背包问题通常可以转化为 0-1 背包问题。

如果第 i 种物品最多有 $M_i$ 个，也就是每种物品的数量有限，那么这类背包问题称为有界背包问题（也可以称为多重背包问题）。如果每种物品的数量都是无限的，那么这类背包问题称为无界背包问题（也可以称为完全背包问题）。

下面通过几个典型的题目来分析如何根据题目的特点确定背包问题的类型并加以解决。

面试题 101 : 分割等和子集

题目：

给定一个非空的正整数数组，请判断能否将这些数字分成和相等的两部分。例如，如果输入数组为 [3, 4, 1]，将这些数字分成 [3, 1] 和 [4] 两部分，它们的和相等，因此输出 true；如果输入数组为 [1, 2, 3, 5]，则不能将这些数字分成和相等的两部分，因此输出 false。

分析：

如果能够将数组中的数字分成和相等的两部分，那么数组中所有数字的和（记为 sum）应该是一个偶数。也可以换一个角度来描述这个问题：能否从数组中选出若干数字，使它们的和等于 sum / 2（将 sum / 2 记为 target）？

如果将数组中的每个数字看成物品的重量，也可以这样描述这个问题：能否选择若干物品，使它们刚好放满一个容量为 target 的背包？由于每个物品（数字）最多只能选择一次，因此这是一个 0-1 背包问题。

传统的 0-1 背包问题要求选择的物品的重量之和不能超过背包的总容量，而这道题则要求选择的物品的重量之和等于背包的总容量。

如果有 n 个物品，每步判断一个物品是否要放入背包，也就是说解决这个问题需要 n 步，并且每步都面临放入或不放入两个选择，这看起来是一个能用回溯法解决的问题。但这个题目没有要求列出所有可能的放满背包的方法，而是只要求判断是否存在放满背包的方法，也就是判断方法的数量是否大于 0。因此，这个问题更适合用动态规划解决。

分析确定状态转移方程：

应用动态规划的关键在于确定状态转移方程。可以用函数 f(i, j) 表示能否从标号为 0 的物品到标号为 i（0 <= i < n）的物品中选择若干物品放满容量为 j（0 <= j <= target）的背包。如果总共有 n 个物品，背包容量为 target，那么 f(n - 1, target) 就是问题的解。

当判断能否从标号为 0 的物品到标号为 i 的物品中选择若干物品放满容量为 j 的背包时，对标号为 i 的物品有两个选择。

不将标号为 i 的物品放入背包中，如果能从标号为 0的物品到标号为 i - 1 的物品中选择若干物品放满容量为 j 的背包（即 f(i - 1, j) 为 true），那么 f(i, j) 也为 true。

前提：i > 0。
将标号为 i 的物品放入背包中，如果能从标号为 0 的物品到标号为 i - 1 的物品中选择若干物品放满容量为 j - nums[i] 的背包（即 f(i - 1, j - nums[i]) 为 true），那么 f(i, j) 就为 true。

前提：i > 0 && j >= nums[i]。

当 i 等于 0 时，f(0, 0) 为 true；f(0, nums[0]) 为 true；f(0, j) = false，j != 0, nums[0]。 $\begin{cases} f(0, 0) = f(0, nums[0]) = true \\ f(0, j) = false, j \neq 0, nums[0] \\ f(i, j) = f(i - 1, j), i > 0 \ \&\& \ j < nums[i] \\ f(i, j) = f(i - 1, j) \ || \ f(i - 1, j - nums[i]), i > 0 \ \&\& \ j \ge nums[i] \end{cases}$

判断能否将数组 [3, 4, 1] 分成和相等的两部分的过程：

i \ j	0	1	2	3	4
0	true	false	false	true	false
1	true	false	false	true	true
2	true	true	false	true	true

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (int num : nums)
        {
            sum += num;
        }
        if (sum % 2)
            return false;
        
        int n = nums.size();
        int target = sum / 2;
        vector<vector<bool>> dp(n, vector<bool>(target + 1, false));
        dp[0][0] = true;
        if (nums[0] > target)
            return false;
        else
            dp[0][nums[0]] = true;
        
        for (int i = 1; i < n; ++i)
        {
            for (int j = 0; j <= target; ++j)
            {
                dp[i][j] = dp[i - 1][j];
                if (!dp[i][j] && j >= nums[i])
                    dp[i][j] = dp[i - 1][j - nums[i]];
            }
        }
        return dp[n - 1][target];
    }
};

上述代码的时间复杂度和空间复杂度都是 O(n * target)。

优化空间效率：

可以优化空间效率。需要注意的是，上述代码在计算 f(i, j) 时，只需要用到行号为 i - 1 的值，因此保存表格中的两行就可以。可以创建一个只有两行的数组 dp，f(i, j) 保存在 dp[i % 2][j] 中。

还可以进一步优化空间效率。如果 f(i, j) 和 f(i - 1, j) 可以保存到数组的同一个位置，那么只需要一个一维数组。

如果按照从左到右的顺序填充表格，f(i - 1, j) 在计算完 f(i, j) 之后还可能在计算右边其他值时被用到，那么不能直接用 f(i, j) 替换 f(i - 1, j)。
但是如果按照从右到左的顺序填充表格，f(i - 1, j) 在计算完 f(i, j) 之后就再也用不到，f(i - 1, j) 被 f(i, j) 直接替换掉不会引起任何问题。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (int num : nums)
        {
            sum += num;
        }
        if (sum % 2)
            return false;
        
        int n = nums.size();
        int target = sum / 2;
        vector<bool> dp(target + 1, false);
        dp[0] = true;
        if (nums[0] > target)
            return false;
        else
            dp[nums[0]] = true;
        
        for (int i = 1; i < n; ++i)
        {
            for (int j = target; j >= nums[i]; --j)
            {
                dp[j] = dp[j] || dp[j - nums[i]];
            }
        }
        return dp[target];
    }
};

优化之后的代码的时间复杂度仍然是 O(n * target)，空间复杂度则变成了 O(target)。

面试题 102 : 加减的目标值

题目：

给定一个非空的正整数数组和一个目标值 target，如果为每个数字添加 "+" 或 "-" 运算符，请计算有多少种方法可以使这些整数的计算结果为 target。例如，如果输入数组 [2, 2, 2] 并且 target 等于 2，有 3 种添加 "+" 或 "-" 的方法使结果为 2，它们分别是 2 + 2 - 2 = 2、2 - 2 + 2 = 2 及 -2 + 2 + 2 = 2。

分析：

在分析解决这个问题之前，需要先做数学运算。为输入的数组中的有些数字添加 "+"，有些数字添加 "-"。如果所有添加 "+" 的数字之和为 p，所有添加 "-" 的数字之和为 q，按照题目的要求 p - q = target ①。将数组中所有数字之和记为 sum，则 p + q = sum ②。将 ① 和 ② 等式的左右两边分别相加，就可以得到 2p = target + sum，即 p = (target + sum) / 2 ③。

等式 ③ 表明，如果能够找出数组中和为 (target + sum) / 2 的数字，并给它们添加 "+"，然后给其他数字添加 "-"，那么最终的计算结果就是 target。因此，这个题目等价于计算从数组中选出和为 (target + sum) / 2 的数字的方法的数目。这和面试题 101 非常类似，是一个典型的 0-1 背包问题，可以用动态规划解决。

分析确定状态转移方程：

用动态规划解决问题的关键在于确定状态转移方程。可以用函数 f(i, j) 表示在数组的前 i + 1 个数字（即 nums[0···i]，0 <= i < n）中选出若干数字使和等于 j（0 <= j <= p）的方法的数目。如果数组的长度为 n，目标值为 p，那么 f(n - 1, p) 就是整个问题的解。

这个问题的状态转移方程和面试题 101 的非常类似，区别在于这里的 f(i, j) 的值不再只是一个 true 或 false 的标识，而是一个数值。 $\begin{cases} f(0, 0) = f(0, nums[0]) = 1, nums[0] \neq 0 \\ f(0, 0) = f(0, nums[0]) = 2, nums[0] = = 0 \\ f(0, j) = 0, j \neq 0, nums[0] \\ f(i, j) = f(i - 1, j), i > 0 \ \&\& \ j < nums[i] \\ f(i, j) = f(i - 1, j) + f(i - 1, j - nums[i]), i > 0 \ \&\& \ j >= nums[i] \end{cases}$

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (int num : nums)
        {
            sum += num;
        }
        if ((target + sum) % 2 || sum < target)
            return 0;
        
        int p = (target + sum) / 2;
        vector<int> dp(p + 1, 0);
        dp[0] = 1;
        if (nums[0] <= p)
            dp[nums[0]] = 1;
        
        if (nums[0] == 0)
            dp[0] = 2;
        
        for (int i = 1; i < nums.size(); ++i)
        {
            for (int j = p; j >= nums[i]; --j)
            {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[p];
    }
};

上述代码的时间复杂度是 O(n * p)，空间复杂度是 O(p)。

面试题 103 : 最少的硬币数目

题目：

给定正整数数组 coins 表示硬币的面额和一个目标总额 amount，请计算凑出总额 amount 至少需要的硬币数目。每种硬币可以使用任意多枚。如果不能用输入的硬币凑出给定的总额，则返回 -1。例如，如果硬币的面额为 [1, 3, 9, 10]，总额 amount 为 15，那么至少需要 3 枚硬币，即 2 枚面额为 3 的硬币及 1 枚面额为 9 的硬币。

分析：

如果将每种面额的硬币看成一种物品，而将目标总额看成背包的容量，那么这个问题等价于求背包放满时物品的最少件数。值得注意的是，这里每种面额的硬币可以使用任意多次，因此这个问题不再是 0-1 背包问题，而是一个无界背包问题（也叫完全背包问题）。

方法一

分析和解决完全背包问题的思路与 0-1 背包问题的思路类似。用函数 f(i, j) 表示用前 i + 1 种硬币（coins[0···i]，0 <= i < n）凑出总额为 j（0 <= j <= amount）需要的硬币的最少数目。

当使用 0 枚标号为 i 的硬币时，f(i, j) 等于 f(i - 1, j)（用前 i - 1 种硬币凑出总额为 j 需要的最少硬币数目，再加上 0 枚标号为 i 的硬币）；当使用 1 枚标号为 i 的硬币时，f(i, j) 等于 f(i - 1, j - coins[i]) 加 1（用前 i - 1 种硬币凑出总额为 j - coins[i] 需要的最少硬币数目，再加上 1 枚标号为 i 的硬币）；以此类推，当使用 k 枚标号为 i 的硬币时，f(i, j) 等于 f(i - 1, j - k * coins[i]) 加 k（用前 i - 1 种硬币凑出总额 j - k * coins[i] 需要的最少硬币数目，再加上 k 枚标号为 i 的硬币）。由于目标是求出硬币数目的最小值，因此 f(i, j) 是上述所有情况的最小值。 $\begin{cases} f(0, k * coins[0]) = k, k \ge 0 \ \&\& \ k * coins[0] \le amount \\ f(0, j) = amount + 1, j \neq k * coins[0] \\ f(i, j) = min(f(i - 1, j - k * coins[i]) + k), i > 0 \ \&\& \ k * coins[i] \le j \end{cases}$

每种硬币的面额一定大于或等于 1，如果能用硬币凑出总额 amount，那么需要的硬币数目一定小于或等于 amount。因此，可以用 amount + 1 表示某个面额不能用输入的硬币凑出。

如果硬币有 n 种，目标总额为 amount，那么 f(n - 1, amount) 就是问题的解。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);
        for (int k = 0; k * coins[0] <= amount; ++k)
        {
            dp[k * coins[0]] = k;
        }

        for (int i = 1; i < coins.size(); ++i)
        {
            for (int j = amount; j >= 0; --j)
            {
                for (int k = 1; k * coins[i] <= j; ++k)
                {
                    dp[j] = min(dp[j], dp[j - k * coins[i]] + k);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

上述代码的时间复杂度是 O(n * amount * k)，空间复杂度是 O(amount)。

方法二

还可以换一种角度分析这个问题。用函数 f(i) 表示凑出总额为 i 的硬币需要的最少数目。需要注意的是，这个函数只有一个参数，表示硬币的总额。如果目标总额为 amount，那么 f(amount) 就是整个问题的解。

为了凑出总额为 i 的硬币，有如下选择：在总额为 i - coins[0] 的硬币中添加 1 枚标号为 0 的硬币，此时 f(i) 等于 f(i - coins[0]) + 1（在凑出总额为 i - coins[0] 的最少硬币数的基础上加上 1 枚标号为 0 的硬币）；在总额为 i - coins[1] 的硬币中添加 1 枚标号为 1 的硬币，此时 f(i) 等于 f(i - coins[1]) + 1。以此类推，在总额为 i - coins[n - 1] 的硬币中添加 1 枚标号为 n - 1 的硬币，此时 f(i) 等于 f(i - coins[n - 1])。因为目标是计算凑出总额为 i 的硬币，所以 f(i) 是上述所有情况的最小值。

$f(i) = min(f(i - coins[j]) + 1), coins[j] \le i$

显然，f(0) 等于 0，即凑出总额为 0 至少需要 0 枚硬币。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;

        for (int i = 1; i <= amount; ++i)
        {
            for (int j = 0; j < coins.size(); ++j)
            {
                if (coins[j] <= i)
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

上述代码的时间复杂度是 O(n * amount)，空间复杂度是 O(amount)。

面试题 104 : 排列的数目

题目：

给定一个非空的正整数数组 nums 和一个目标值 target，数组中的所有数字都是唯一的，请计算数字之和等于 target 的所有排列的数目。数组中的数字可以在排列中出现任意次。例如，输入数组 [1, 2, 3]，目标值 target 为 3，那么总共有 4 个排列的数字之和等于 3，它们分别是 { 1, 1, 1 }、{ 1, 2 }、{ 2, 1 } 及 { 3 }。

分析：

如果将数组中的每个数字看成硬币的面额，而将目标值 target 看成总额，那么这个问题和面试题 103 是非常类似的。可以用类似的思路来推导状态转移方程。

用 f(i) 表示数字之和等于 i 的所有排列的数目。

为了得到数字之和等于 i 的所有排列，有如下选择：在数字之和等于 i - nums[0] 的排列中添加标号为 0 的数字，此时 f(i) 等于 f(i - nums[0])；在数字之和等于 i - nums[1] 的排列中添加标号为 1 的数字，此时 f(i) 等于 f(i - nums[1])；以此类推，在数字之和等于 i - nums[n - 1] 的排列中添加标号为 n - 1 的数字（n 为数组的长度），此时 f(i) 等于 f(i - nums[n - 1])。因为目标是求出所有数字之和等于 i 的排列的数目，所以将上述情况全部累加起来。 $f(i) = \sum f(i - nums[j]), i \ge nums[j]$

由于只有一个空排列的数字之和等于 0，因此 f(0) 等于 1。

i	0	1	2	3
f(i)	1	1	2	4
数字之和等于 i 的所有排列	{ }	{ 1 }	{ 1, 1 }、{ 2 }	{ 1, 1, 1 }、{ 2, 1 }、{ 1, 2 }、{ 3 }

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<unsigned int> dp(target + 1);
        dp[0] = 1;

        for (int i = 1; i <= target; ++i)
        {
            for (int j = 0; j < nums.size(); ++j)
            {
                if (i >= nums[j])
                    dp[i] += dp[i - nums[j]];
            }
        }
        return dp[target];
    }
};