算法训练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];
    }
};