算法训练day44完全背包518. 零钱兑换 II377. 组合总和 Ⅳ

本文主要是介绍算法训练day44完全背包518. 零钱兑换 II377. 组合总和 Ⅳ，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

完全背包理论

代码随想录

518. 零钱兑换 II

题目分析

在求装满背包有几种方案的时候，认清遍历顺序是非常关键的。

如果求组合数就是外层for循环遍历物品，内层for遍历背包。

如果求排列数就是外层for遍历背包，内层for循环遍历物品。

acm模式代码

#include <iostream>
#include <vector>class Solution
{
public:int change(int amount, std::vector<int> &coins){std::vector<int> dp(amount + 1, 0);dp[0] = 1;for (int i = 0; i < coins.size(); i++) {for (int j = coins[i]; j <= amount; j++) {dp[j] += dp[j - coins[i]];}}// 求得是排列数// for (int j = 0; j <= amount; j++)// { // 遍历背包容量//     for (int i = 0; i < coins.size(); i++)//     { // 遍历物品//         if (j - coins[i] >= 0)//             dp[j] += dp[j - coins[i]];//     }// }for (int i : dp){std::cout << i << " ";}return dp[amount];}
};int main()
{Solution sol;std::vector<int> coins = {1, 2, 5};int result = sol.change(5, coins);return 0;
}

377. 组合总和 Ⅳ

题目分析

该解法使用了动态规划的方法，创建了一个动态规划数组 dp，其中 dp[i] 表示达到总和为 i 的目标数的组合方式数量。初始化 dp[0] = 1，因为达到总和为 0 的方式只有一种，即不使用任何数字。

然后，算法通过两层循环来填充这个 dp 数组：

1. 外层循环（i 从 0 遍历到 target）: 这个循环遍历所有的目标值，从 0 到 target，对于每一个可能的目标值，尝试找到组合它的所有可能方式。

2. 内层循环（j 遍历 nums 数组）: 对于每一个目标值 i，遍历 nums 数组中的每个数 nums[j]，尝试将其加到之前的组合中。如果当前目标值 i 大于或等于 nums[j]，则 dp[i] 的值应该加上 dp[i - nums[j]] 的值，因为 dp[i - nums[j]] 代表了从 i 减去当前数字 nums[j] 之后的目标值的组合数。注意事项

• 检查 dp[i] < INT_MAX - dp[i - nums[j]] 是为了防止整数溢出。由于 dp[i] 在每次迭代中都可能增加，需要确保加上 dp[i - nums[j]] 不会导致溢出。
• 初始化 dp[0] = 1 是基于组合数学中的一个原理，即“没有”是达到目标总和为 0 的唯一方式。结果

通过填充 dp 数组，最终 dp[target] 中存储的就是使用 nums 数组中的数通过加法组合得到目标数 target 的总方法数。

这种动态规划方法有效地将一个看似复杂的组合问题分解为了更小、更易于管理的子问题，通过解决这些子问题并逐步构建解决方案，最终达到了求解总问题的目的。

代码

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<int> dp(target + 1, 0);dp[0] = 1;for (int i = 0; i <= target; i++) { // 遍历背包for (int j = 0; j < nums.size(); j++) { // 遍历物品if (i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]]) {dp[i] += dp[i - nums[j]];}}}return dp[target];}
};

这篇关于算法训练day44完全背包518. 零钱兑换 II377. 组合总和 Ⅳ的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---