LeetCode题练习与总结：组合总和 Ⅳ --377

一、题目描述

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：

输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

示例 2：

输入：nums = [9], target = 3
输出：0

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 1000
• nums 中的所有元素 互不相同
• 1 <= target <= 1000

二、解题思路

这是一个完全背包问题，其中物品（数组 nums 中的元素）可以重复使用，背包容量为 target，我们需要求的是装满背包的方法数。

我们可以使用动态规划来解决这个问题。定义 dp[i] 表示总和为 i 的元素组合的个数。初始化 dp[0] = 1，因为总和为0的元素组合只有一个，就是什么元素都不使用。

对于 nums 中的每个元素 num，我们需要更新 dp 数组，使得每个 dp[i] 包含使用 num 的所有可能组合。

具体来说，对于每个 i 从 num 到 target，我们可以更新 dp[i] 为 dp[i] + dp[i - num]。这是因为对于每个 i，我们可以选择不使用当前的 num（这样组合数不变，即 dp[i]），或者使用当前的 num（这样组合数增加 dp[i - num]）。

最后，dp[target] 就是我们要找的答案。

三、具体代码

class Solution {
    public int combinationSum4(int[] nums, int target) {
        // dp[i] 表示总和为 i 的元素组合的个数
        int[] dp = new int[target + 1];
        // 总和为 0 的组合只有一个，就是什么都不选
        dp[0] = 1;
        
        // 对于每个可能的组合总和
        for (int i = 1; i <= target; i++) {
            // 遍历每个数字，尝试更新 dp[i]
            for (int num : nums) {
                if (i >= num) {
                    dp[i] += dp[i - num];
                }
            }
        }
        
        // 返回总和为 target 的组合数
        return dp[target];
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

• 我们有一个双重循环，外层循环遍历的是从 1 到 target 的所有可能的总和值，这个循环的次数是 target。
• 内层循环遍历的是数组 nums 中的所有元素，这个循环的次数是 nums.length。
• 因此，总的时间复杂度是外层循环次数乘以内层循环次数，即 O(target * nums.length)。

2. 空间复杂度

• 我们使用了一个数组 dp 来存储从 0 到 target 的所有可能的总和值的组合数。
• 数组 dp 的大小是 target + 1，所以空间复杂度是 O(target)。

五、总结知识点

• 动态规划 (Dynamic Programming, DP):

  • 动态规划是一种用于解决优化问题的算法思想，通过将问题分解为更小的子问题，并将这些子问题的解存储起来以避免重复计算。

• 数组的使用:

  • 数组 dp 用于存储中间结果，即对于每个可能的组合总和，它的组合数是多少。

• 初始化:

  • dp[0] = 1; 表示总和为 0 的组合数是 1，即不选择任何元素。

• 嵌套循环:

  • 外层循环遍历所有可能的组合总和（从 1 到 target）。
  • 内层循环遍历数组 nums 中的每个元素，用于更新 dp 数组。

• 条件判断:

  • if (i >= num) 确保在尝试更新 dp[i] 时，i 至少要大于或等于 num，这是为了避免数组越界和无效的组合。

• 状态转移方程:

  • dp[i] += dp[i - num]; 是状态转移方程，它表示总和为 i 的组合数等于所有可能的前一个状态（即 i - num）的组合数之和。

• 返回值:

  • 最后返回 dp[target]，即总和为 target 的组合数。

• 数组索引的使用:

  • 在内层循环中，通过索引 i - num 来引用之前计算过的组合数，这是动态规划中的一个关键步骤。

• 整数数组:

  • int[] dp = new int[target + 1]; 创建了一个整数数组，其大小为 target + 1，以存储从 0 到 target 的所有组合数。

• 类型转换:

  • 在更新 dp[i] 时，隐含了从 int 到 int 的类型转换，因为 dp[i - num] 也是一个 int 类型的值。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。