一、完全背包（参考博客）
和01背包区别在于物品可以无限次放入背包。完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
因此在需要在遍历顺序上进行区别，参考代码随想录：
二、518.零钱兑换II
题目求的是组合数目，和常见的完全背包问题，求最大价值不一样。
还是动态规划几个步骤。
1 定义dp[j]，表示j数字下，能组合成j的组合数目。
2 状态方程：dp[j]由dp[j - coins[i]]转移得到，即：
dp[j] += dp[j - coins[i]]
3 初始化dp[0] = 1，如果等于0，那么累加依旧等于0,其余值为0；
4 返回dp[amount];
5 dp循环验证；
int change(int amount, int* coins, int coinsSize) {
//保证第一个为1，其余为0
int* dp = (int*)calloc(amount + 1, sizeof(int));
dp[0] = 1;
for(int i = 0; i < coinsSize; i++)
{
for(int j = coins[i]; j <= amount; j++)
{
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}三、377. 组合总和 Ⅳ
给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
注意：这里组合其实可以理解成排列，因为顺序不同数字相同也看作一个组合方式。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
和前面一样，需要动态规划的步骤：
1 设置dp[j],代表数字j的组合个数；
2 状态转移：
dp[j] += dp[j - nums[i]];
3 初始化时候，dp[0] = 1,其余初始化为0;
4 遍历顺序，如上for循环顺序。
int combinationSum4(int* nums, int numsSize, int target) {
//保证第一个为1，其余为0
int* dp = (int*)calloc(target + 1, sizeof(int));
dp[0] = 1;
for(int j = 0; j <= target; j++)
{
for(int i = 0; i < numsSize; i++)
{
if(j >= nums[i])
dp[j] += dp[j - nums[i]];
}
}
return dp[target];
}四、322. 零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。
注意题目所求的是最少得硬币个数。
动态规划步骤：
1 dp[j]代表j数最少的硬币个数；
2 动态转移公式：
dp[j] = min(dp[j], dp[j - coins[i]] + 1)
3 初始化：dp[0] = 0，凑成0的个数为0，其余应该是INT_MAX;
4 遍历顺序，先遍历物品，再遍历value；
#define MIN(a, b) (a) > (b)? (b): (a)
int coinChange(int* coins, int coinsSize, int amount) {
int* dp = (int*)malloc(sizeof(int) * (amount + 1));
for(int i = 0; i <= amount; i++)
{
dp[i] = INT_MAX;
}
dp[0] = 0;
for(int i = 0; i < coinsSize; i++)
{
for(int j = coins[i]; j <= amount; j++)
{
if(dp[j - coins[i]] == INT_MAX)
continue;
dp[j] = MIN(dp[j], dp[j - coins[i]] + 1);
}
}
return dp[amount] == INT_MAX? -1 : dp[amount];
}五、279.完全平方数
给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
思路：完全平方数看作物品，n代表背包，物品可以多次放入。
1 dp[j] 代表j的最小数量完全平方数；
2 状态转移公式：
dp[j] = min(dp[j], dp[j - i * i] +1);
3 初始化：dp[0] = 0, 其余值为INT_MAX;
4 循环顺序 先遍历物品，再遍历价值
#define MIN(a, b) (a) > (b)? (b): (a)
int numSquares(int n) {
int* dp = (int*)malloc(sizeof(int) * (n + 1));
for(int i = 0; i <= n; i++)
{
dp[i] = INT_MAX;
}
dp[0] = 0;
for(int i = 1; i*i <= n; i++)//注意边界
{
for(int j = i*i; j <= n; j++)//注意起点，按照含义来理解
{
dp[j] = MIN(dp[j], dp[j - i*i] + 1);
}
}
return dp[n] == INT_MAX? -1 : dp[n];
}
