永久免费搭建网站,做网站侵权,中国企业100强,山东专业网站建设哪家便宜问题
注#xff1a;大佬对此类问题的解法#xff1a;动态规划背包问题总结 给你一个由 不同 整数组成的数组 nums #xff0c;和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
示例 1#xff…问题
注大佬对此类问题的解法动态规划背包问题总结 给你一个由 不同 整数组成的数组 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
程序
#include stdio.h// 定义一个函数来计算总和为目标整数的元素组合的个数
int combinationSum4(int* nums, int numsSize, int target) {// 创建一个动态规划数组 dp长度为 target 1int dp[target 1];// 初始化 dp 数组将所有元素初始化为0for (int i 0; i target; i) {dp[i] 0;}// 初始状态总和为0时只有一种组合方式即什么都不选dp[0] 1;// 开始填充 dp 数组for (int i 1; i target; i) {for (int j 0; j numsSize; j) {// 如果当前的目标总和减去数组元素可达if (i - nums[j] 0) {// 则将 dp[i] 增加 dp[i - nums[j]]表示加上当前元素后的组合数dp[i] dp[i - nums[j]];}}}// 返回 dp 数组中最终目标总和的组合数return dp[target];
}int main() {int nums[] {1, 2, 3};int target 4;int numsSize sizeof(nums) / sizeof(nums[0]);// 调用 combinationSum4 函数计算组合数int result combinationSum4(nums, numsSize, target);// 打印结果printf(输出%d\n, result);return 0;
}
解释
在动态规划中dp[i - nums[j]] 表示以目标值 i 减去数组中的某个元素 nums[j] 后的状态。这通常用于动态规划问题中特别是在处理组合问题时来记录前一步的状态。
在上述程序中dp[i] 表示总和为 i 的组合数。当计算 dp[i] 时我们遍历数组 nums 中的元素对于每个元素 nums[j]我们考虑将其加入总和为 i 的组合中。为了计算 dp[i]我们需要考虑两种情况
如果 i 大于等于 nums[j]那么我们可以将 nums[j] 加入到总和为 i 的组合中。此时我们需要考虑的是将 nums[j] 加入后剩余的总和为 i - nums[j] 的组合数这就是 dp[i - nums[j]]。如果 i 小于 nums[j]则 nums[j] 不能被加入到总和为 i 的组合中因为它会导致总和超过 i。因此在这种情况下dp[i - nums[j]] 为0。
所以dp[i - nums[j]] 表示以目标值 i 减去数组中的某个元素 nums[j] 后的状态即剩余的部分。通过考虑所有可能的 nums[j]我们可以累加所有这些情况以计算总和为 i 的组合数 dp[i]。这就是动态规划的思想将较大问题分解成较小问题并使用较小问题的解来构建较大问题的解。
假设数组 nums 为 [1, 2, 3]目标值 target 为 4。 初始时dp 数组如下
dp[0] 1
dp[1] 0
dp[2] 0
dp[3] 0
dp[4] 0
开始计算 dp[1]
i 等于 1nums[j] 等于 1因此 i nums[j]。我们考虑将 1 加入到总和为 1 的组合中剩余的总和是 1 - 1 0。此时dp[0] 为1因为只有一种组合方式即什么都不选。所以dp[1] dp[1 - 1] dp[0] 1。 继续计算 dp[2] 和 dp[3]dp[2] 的计算和 dp[1] 类似因为我们可以将 2 加入到总和为 2 的组合中dp[2] dp[2 - 2] dp[0] 1。dp[3] 的计算也类似因为我们可以将 3 加入到总和为 3 的组合中dp[3] dp[3 - 3] dp[0] 1。 最后计算 dp[4]对于 dp[4]我们可以考虑将 1 加入到总和为 4 的组合中这就是 dp[4 - 1] dp[3] 1。我们还可以考虑将 2 加入到总和为 4 的组合中这就是 dp[4 - 2] dp[2] 1。同样我们可以考虑将 3 加入到总和为 4 的组合中这就是 dp[4 - 3] dp[1] 1。然后将这些情况的组合数累加起来即 dp[4] 1 1 1 3。
最终dp[4] 的值为 3表示总和为 4 的组合数为 3 种即 [1, 1, 1, 1]、[1, 1, 2] 和 [2, 2]。
