花溪建设村镇银行官方网站,wordpress 发布时,页面跳转的方法,石大网页设计与网站建设文档讲解#xff1a;完全背包理论基础 零钱兑换II 组合总和IV 518.零钱兑换II
题目链接#xff1a;https://leetcode.cn/problems/coin-change-ii/description/
思路#xff1a; 这是一道典型的背包问题#xff0c;一看到钱币数量不限#xff0c;就知道这是一个完全背… 文档讲解完全背包理论基础 零钱兑换II 组合总和IV 518.零钱兑换II
题目链接https://leetcode.cn/problems/coin-change-ii/description/
思路 这是一道典型的背包问题一看到钱币数量不限就知道这是一个完全背包。 但本题和纯完全背包不一样纯完全背包是凑成背包最大价值是多少而本题是要求凑成总金额的物品组合个数 设dp[j]凑成总金额j的货币组合数为dp[j] dp[j] 就是所有的dp[j - coins[i]]考虑coins[i]的情况相加。 所以递推公式dp[j] dp[j - coins[i]]; 初始化dp[0]为1即可。
核心代码
class Solution {
public:int change(int amount, vectorint coins) {vectorint dp(amount 1, 0);dp[0] 1;for (int i 0; i coins.size(); i) { // 遍历物品for (int j coins[i]; j amount; j) { // 遍历背包dp[j] dp[j - coins[i]];}}return dp[amount];}
};
377.组合总和IV
题目链接https://leetcode.cn/problems/combination-sum-iv/description/
思路 设dp[i]: 凑成目标正整数为i的排列个数为dp[i] dp[i]考虑nums[j]可以由 dp[i - nums[j]]不考虑nums[j] 推导出来。 因为只要得到nums[j]排列个数dp[i - nums[j]]就是dp[i]的一部分。 dp[0]要初始化为1这样递归其他dp[i]的时候才会有数值基础。非0下标的dp[i]应该初始化为0这样才不会影响dp[i]累加所有的dp[i - nums[j]]。 遍历顺序target背包放在外循环将nums物品放在内循环内循环从前到后遍历。
核心代码
class Solution {
public:int combinationSum4(vectorint nums, int target) {vectorint dp(target 1, 0);dp[0] 1;for (int i 0; i target; i) { // 遍历背包for (int j 0; j nums.size(); j) { // 遍历物品if (i - nums[j] 0 dp[i] INT_MAX - dp[i - nums[j]]) {dp[i] dp[i - nums[j]];}}}return dp[target];}
};
今日总结 今日学习时长2h接着八股文。 主管面通过开心没想到过了。
