各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 85 天。今天力扣上的每日一题是「377. 组合总和 Ⅳ」。

解题思路

题意：从输入的 nums 数组中挑选数字（可重复）使得这些数字的和是 target ，求有多少种组合方法。

今天这个题目有个明显的提示：求组合的个数，而不是每个组合。如果是要求出每个组合，那么必须使用回溯法，保存所有路径。但是如果是组合个数，一般都应该想到「动态规划」的解法。

直接写出「动态规划」的解法，我认为是有一定难度的。不妨先写出「记忆化递归」，然后修改为「动态规划」。

递归

要求构成 target 有多少种组合方法，这里的变量应该是 target，所以，令函数 **dp(x)**表示从 nums 中挑选数字可以构成 x 的方法数（递归最基本的就是理解这个定义！）。最终返回的应该是 dp(target)。

对于题目输入 nums = [1,2,3], target = 4 时：要求有多少种方法能够成 4，即要求 dp(4)。思考过程如下。

我们遍历 nums，判断如果构成 target 的时候，选择了 nums[i]，那么剩余的 target - nums[i] 仍在 nums 中选的话，会有多少种方法。

  • 对于 nums[0] = 1， 我们要求有多少种方法能够成 target - nums[0] = 4 - 1 = 3，即要求 dp(3)；
  • 对于 nums[1] = 2, 我们要求有多少种方法能够成 target - nums[1] = 4 - 2 = 2，即要求 dp(2)；
  • 对于 nums[2] = 3, 我们要求有多少种方法能够成 target - nums[2] = 4 - 3 = 1，即要求 dp(1)；

所以，dp(4) = dp(3) + dp(2) + dp(1)。然后调用函数继续求解 dp(3), dp(2) 和 dp(1)。

发现出现了递归！这就是我在每个用到递归的题解中都会说的，把大问题拆分成小问题，然后发现小问题恰好可以用同样的函数解决，于是构成了递归。递归是一种现象，绝不是为了递归而递归。

那么递归终止条件是什么呢？也就是说最基础的case应该直接返回什么结果呀？

  • 题目给出的数字都是正整数，因此如果当要求的 target < 0 的时候，无论如何都无法从数组中挑选元素构成，所以应该返回 0 ；
  • 当要求的 target == 0 的时候，需要 return 1；为什么呢？因为我们注意题目给出的输入 target 一定是大于 0 的，如果在递归的时候 target == 0，说明在 for 循环中的 target - num 得到了 0，表示 nums 数组中恰好有一个数字等于 target。所以返回 1。

递归代码如下，提交的时候会超时。

  1. class Solution(object):
  2.     def combinationSum4(self, nums, target):
  3.         if target < 0:
  4.             return 0
  5.         if target == 0:
  6.             return 1
  7.         res = 0
  8.         for num in nums:
  9.             res += self.combinationSum4(nums, target - num)
  10.         return res
  • 时间复杂度：$O(N^target)$，N 是 nums 的长度。每次递归需要计算 N 次，递归深度最多 target 。
  • 空间复杂度：$O(target)$

记忆化递归

上面的递归方法会超时，是因为有重复计算，比如计算 dp(4) 的时候计算了 dp(2)，而计算 dp(3) 的时候会再次计算 dp(2)。如果我们在递归的过程中，把已经计算了的结果放在数组/字典中保存，那么下次需要再次计算相同的值的时候，直接从数组/字典中读取同样的计算结果，就能省下很多计算。

下面的代码演示了如何使用「记忆化递归」。定义了一个 dp 数组，保存已经计算了的每个 dp(x)。 dp 数组的每个位置初始化为 -1， 表示还没有计算过。在递归函数刚开始的时候，不仅要判断 target 是否 < 0，还要判断当前计算的 target 是否计算过（即 dp[target] != -1）。只有在没计算过的情况下，才执行递归。并且在执行递归之后，需要把当前 target 的计算结果保存到 dp 数组中。

  1. class Solution(object):
  2.     def combinationSum4(self, nums, target):
  3.         self.dp = [-1] * (target + 1)
  4.         self.dp[0] = 1
  5.         return self.dfs(nums, target)
  7.     def dfs(self, nums, target):
  8.         if target < 0: return 0
  9.         if self.dp[target] != -1:
  10.             return self.dp[target]
  11.         res = 0
  12.         for num in nums:
  13.             res += self.dfs(nums, target - num)
  14.         self.dp[target] = res
  15.         return res
  • 时间复杂度：$O(N*target)$，N 是 nums 的长度。对于每个 target 求解的时候，只用遍历一次 dp 数组。
  • 空间复杂度：$O(target)$

动态规划

理解了「记忆化递归」之后，写出动态规划只有一步之遥。递归是自顶向下的计算方式（大问题->小问题），而动态规划是自底向上的计算方式（小问题->大问题）。

动态规划也同样地定义 dp 数组，dp[i] 表示从 nums 中抽取元素组成 target 的方案数。dp 数组的长度是 target + 1。其中 dp[0] 表示从数组中抽取任何元素组合成 0 的方案数，根据我们在递归时的分析，我们知道需要令 dp[0] = 1。其他位置的 dp[i] 需要初始化为 0，表示我们还没有计算过这个位置，默认的方案数为0。

想要计算得到 target，需要把 dp[1~target] 的各个元素都计算出来。每个位置的计算都是为了后面的计算做准备。

动态规划的代码如下，是从记忆化递归改造而来。

  1. class Solution(object):
  2.     def combinationSum4(self, nums, target):
  3.         dp = [0] * (target + 1)
  4.         dp[0] = 1
  5.         res = 0
  6.         for i in range(target + 1):
  7.             for num in nums:
  8.                 if i >= num:
  9.                     dp[i] += dp[i - num]
  10.         return dp[target]
  1. class Solution {
  2. public:
  3.     int combinationSum4(vector<int>& nums, int target) {
  4.         vector<int> dp(target + 1, 0);
  5.         dp[0] = 1;
  6.         for (int i = 1; i <= target; i++) {
  7.             for (auto a : nums) {
  8.                 if (i >= a) {
  9.                     dp[i] += dp[i - a];
  10.                 } 
  11.             }
  12.         }
  13.         return dp.back();
  14.     }
  15. };
  • 时间复杂度：$O(N*target)$，N 是 nums 的长度。两重 for 循环，循环次数分别为 target 和 N。
  • 空间复杂度：$O(target)$

刷题心得

「动态规划」是由「记忆化递归」改进而来，一般题解只告诉你这个题要用「动态规划」，但是没解释怎么想到「动态规划」，因为没说想法来自「记忆化递归」。我的建议是，不妨先写出「记忆化递归」，然后再改造成「动态规划」。大部分题目的「记忆化递归」就能通过了，比如本题。

参考资料：
花花酱
负雪明烛

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家 AC 多多，Offer 多多！我们明天再见！