代码随想录第44天|●518.零钱兑换II●377.组合总和Ⅳ-创新互联

一看到钱币数量不限，就知道这是一个完全背包。
但本题和纯完全背包不一样，纯完全背包是凑成背包大价值是多少，而本题是要求凑成总金额的物品组合个数！
组合不强调元素之间的顺序，排列强调元素之间的顺序

dp[j] 就是所有的dp[j - coins[i]]（考虑coins[i]的情况）相加。
所以递推公式：dp[j] += dp[j - coins[i]];

首先dp[0]一定要为1，dp[0] = 1是 递归公式的基础。如果dp[0] = 0 的话，后面所有推导出来的值都是0了。

遍历顺序必须是先物品后背包，这样是组合
如果是先背包，后物品，就是排序了，打印数组可以看出来

其实就是518.零钱兑换2的先遍历背包后遍历物品，求排列
一样一样的
C++测试用例有两个数相加超过int的数据，所以需要在if里加上dp[i]< INT_MAX - dp[i - num]。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧