本文主要是介绍算法训练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 数组：
-
外层循环（
i从 0 遍历到target）: 这个循环遍历所有的目标值，从 0 到target，对于每一个可能的目标值，尝试找到组合它的所有可能方式。 -
内层循环（
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. 组合总和 Ⅳ的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
