重庆分公司
重庆分公司，新征程启航
为企业提供网站建设、域名注册、服务器等服务
代码随想录第44天|●518.零钱兑换II●377.组合总和Ⅳ-创新互联
518.零钱兑换2
377.组合总和4
当前标题：代码随想录第44天|●518.零钱兑换II●377.组合总和Ⅳ-创新互联
当前地址：http://cqcxhl.cn/article/dogdhi.html
一看到钱币数量不限，就知道这是一个完全背包。
但本题和纯完全背包不一样，纯完全背包是凑成背包大价值是多少，而本题是要求凑成总金额的物品组合个数！
组合不强调元素之间的顺序，排列强调元素之间的顺序
dp[j] 就是所有的dp[j - coins[i]]（考虑coins[i]的情况）相加。
所以递推公式：dp[j] += dp[j - coins[i]];
首先dp[0]一定要为1，dp[0] = 1是 递归公式的基础。如果dp[0] = 0 的话，后面所有推导出来的值都是0了。
遍历顺序必须是先物品后背包，这样是组合
如果是先背包，后物品，就是排序了，打印数组可以看出来
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 1(1,1) | 2(1,1,1)(2,1) | ||
| 2 | 1 | 1 | 2 (1,1)(2) | 3(1,1,1)(2,1)(1,2) | ||
| 5 | 1 | 1 | 2 | 3 |
其实就是518.零钱兑换2的先遍历背包后遍历物品，求排列
一样一样的
C++测试用例有两个数相加超过int的数据，所以需要在if里加上dp[i]< INT_MAX - dp[i - num]。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
当前标题：代码随想录第44天|●518.零钱兑换II●377.组合总和Ⅳ-创新互联
当前地址：http://cqcxhl.cn/article/dogdhi.html