简述建设一个网站的基本步骤,网站建设周记,百度关键词推广网站,可信网站认证 费用377. 组合总和 Ⅳ 文章目录 [377. 组合总和 Ⅳ](https://leetcode.cn/problems/combination-sum-iv/)一、题目二、题解方法一#xff1a;完全背包一维数组动态规划思路代码分析 方法二#xff1a;动态规划二维数组 一、题目
给你一个由 不同 整数组成的数组 nums #xff0…377. 组合总和 Ⅳ 文章目录 [377. 组合总和 Ⅳ](https://leetcode.cn/problems/combination-sum-iv/)一、题目二、题解方法一完全背包一维数组动态规划思路代码分析 方法二动态规划二维数组 一、题目
给你一个由 不同 整数组成的数组 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 2001 nums[i] 1000nums 中的所有元素 互不相同1 target 1000
进阶如果给定的数组中含有负数会发生什么问题会产生何种变化如果允许负数出现需要向题目中添加哪些限制条件
二、题解
这道题要求我们找出由给定数组 nums 中的不同元素组成的总和等于 target 的组合个数说是组合其实实质上是排列我在这篇文章里讲述了关于排列组合的区别并且手写了动态规划过程https://blog.csdn.net/m0_61843614/article/details/132745696。
方法一完全背包一维数组
动态规划思路
定义一个一维数组 dp其中 dp[i] 表示总和为 i 的组合个数。
我们的目标是计算 dp[target]也就是总和为 target 的组合个数。为了计算 dp[target]可以考虑如下的思路 初始化一个长度为 target 1 的数组 dp并将其所有元素初始化为0。dp[i] 表示总和为 i 的组合个数。 由于组合的元素可以重复使用我们可以遍历数组 nums 中的每个元素并尝试将其加入到总和为 i 的组合中。 对于每个元素 nums[j]我们可以检查 dp[i - nums[j]]它表示总和为 i - nums[j] 的组合个数。我们可以将 dp[i - nums[j]] 加到 dp[i] 上表示将 nums[j] 加入到当前组合中。 重复上述步骤直到遍历完数组 nums 中的所有元素。 最终dp[target] 就是我们要求的答案表示总和为 target 的组合个数。
代码分析
class Solution {
public:int combinationSum4(vectorint nums, int target) {vectorlong long dp(target 1, 0);dp[0] 1; // 初始化总和为0的组合个数为1for (int i 0; i target; i) {for (int j 0; j nums.size(); j) {if (nums[j] i dp[i] INT_MAX - dp[i - nums[j]]) {dp[i] dp[i] dp[i - nums[j]]; // 更新 dp[i]}}}return dp[target];}
};现在我逐步解释代码的各个部分 我们定义了一个一维数组 dp长度为 target 1并将所有元素初始化为0。 初始化 dp[0] 为1因为总和为0的组合只有一种方式就是什么都不选。 使用两个嵌套的循环外层循环遍历所有可能的总和 i内层循环遍历数组 nums 中的所有元素。 在内层循环中我们检查当前元素 nums[j] 是否小于等于 i如果是就说明可以将 nums[j] 加入到总和为 i 的组合中。 如果 dp[i] 的值还没有越界小于 INT_MAX - dp[i - nums[j]]则将 dp[i - nums[j]] 的值加到 dp[i] 上表示将 nums[j] 加入到当前组合中。 最终返回 dp[target]即总和为 target 的组合个数。
方法二动态规划二维数组
先给出代码
class Solution {
public:int combinationSum4(vectorint nums, int target) {//dp[j][i]意义是背包容量为i的情况下最后一个加入的数字是从nums[0]到nums[i]之间的方法的总数vectorvectorlong long dp(nums.size(), vectorlong long(target 1, 0));dp[0][0] 1;for (int i 0; i target; i) {for (int j 0; j nums.size(); j) {if (j 0) {dp[j][i] dp[j - 1][i];}if (i nums[j] dp[j][i] INT_MAX - dp[nums.size() - 1][i - nums[j]]) {dp[j][i] dp[nums.size() - 1][i - nums[j]];}}}return dp[nums.size() - 1][target];}
};动态规划思路
这个问题的目标是找出总和为 target 的元素组合的个数。首先让我们定义一个二维数组 dp其中 dp[j][i]意义是背包容量为i的情况下最后一个加入的数字是从nums[0]到nums[i]之间的方法的总数。我们的目标是求 dp[nums.size() - 1][target]即使用所有的元素构成和为 target 的排列的个数。
初始化
首先我们初始化 dp 数组将所有元素都初始化为 0。然后我们设置 dp[0][0] 1这是因为在前 0 个元素中构成和为 0 的组合有一种方式即不选择任何元素。
填充动态规划数组
接下来我们使用两个嵌套循环来填充 dp 数组。外层循环 i 表示考虑前 i 个元素内层循环 j 表示目标和为 j。 如果 j nums[i]意味着当前的元素 nums[i] 太大不能加入组合中所以我们将 dp[i][j] 设置为 dp[i-1][j]表示不选择当前元素时的组合数继承上一行的值。 如果 j nums[i]意味着当前的元素 nums[i] 可以加入组合中。我们需要考虑两种情况 不选择当前元素即 dp[i][j] dp[i-1][j]。选择当前元素即 dp[i][j] dp[i][j - nums[i]]这里的 dp[i][j - nums[i]] 表示在考虑前 i 个元素和为 j - nums[i] 的组合数。
最终dp[nums.size() - 1][target] 就代表了使用所有元素构成和为 target 的组合的个数。
返回结果
最后我们返回 dp[nums.size() - 1][target] 即可得到答案。
