课程网站建设内容,app推广接单发布平台,网站模板双语,十大待遇最好央企一、完全背包#xff08;参考博客#xff09;
和01背包区别在于物品可以无限次放入背包。完全背包和01背包问题唯一不同的地方就是#xff0c;每种物品有无限件。
因此在需要在遍历顺序上进行区别#xff0c;参考代码随想录#xff1a; 二、518.零钱兑换II
题目求的是组…一、完全背包参考博客
和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其余为0int* 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其余为0int* 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];
}
