518.零钱兑换2

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

创新互联是一家专业提供河口企业网站建设,专注与网站设计、成都网站建设、HTML5、小程序制作等业务。10年已为河口众多企业、政府机构等服务。创新互联专业网站制作公司优惠进行中。

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

377.组合总和4

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

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

本文标题：代码随想录第44天|●518.零钱兑换II●377.组合总和Ⅳ-创新互联
分享网址：http://chengdu.cdxwcx.cn/article/dogdhi.html