网站的按钮怎么做的,网站发布与推广怎么写,wordpress 同类文章,外贸网站建设网站文章目录 518.零钱兑换II思路代码实现 377. 组合总和 Ⅳ思路代码实现 518.零钱兑换II
题目链接
思路
确定dp数组#xff08;dp table#xff09;以及下标的含义 dp[j]#xff1a;组合元素和为j的组合方式确定递推公式 题目不是选取最优解#xff0c;而是求路径总和… 文章目录 518.零钱兑换II思路代码实现 377. 组合总和 Ⅳ思路代码实现 518.零钱兑换II
题目链接
思路
确定dp数组dp table以及下标的含义 dp[j]组合元素和为j的组合方式确定递推公式 题目不是选取最优解而是求路径总和则取不同数字的零钱coin[i]时都有dp[j-coin[i]]种方法 则dp[j]dp[j-coin[i]]dp数组如何初始化 后台题目要求是dp[0]1这里题目没给出准确的说法确定遍历顺序 外层for循环从前往后内层for循环也是从前往后 这和01背包完全不同根本原因就是这里的钱每个面额的数量都没有限制所以可以重复选取 但外层for循环和内存for循环不可以调换因为现在是先遍历钱钱是不会出现{5,1}和{1,5}这样的重复现象的但如果钱变成内层for循环的话就可以重复选取这就是后面那道题的排列问题举例推导dp数组
代码实现
class Solution {
public:int change(int amount, vectorint coins) {vectorint dp(10010,0);dp[0]1;for(int i0;icoins.size();i){for(int jcoins[i];jamount;j){dp[j]dp[j-coins[i]];}}return dp[amount];}
};377. 组合总和 Ⅳ
题目链接
思路
这道题就是排列问题
确定dp数组dp table以及下标的含义 dp[j]组合元素和为j的组合方式确定递推公式 题目不是选取最优解而是求路径总和则取不同数字的零钱coin[j]时都有dp[i-coin[j]]种方法 则dp[i]dp[i-coin[j]]dp数组如何初始化 后台题目要求是dp[0]1这里题目没给出准确的说法确定遍历顺序 外层for循环从前往后内层for循环也是从前往后 这就是排列问题{5,1}和{1,5}都是正确结果。而钱变成内层for循环的话就可以重复选取。先遍历背包容量当容量允许装入背包就可以累加记录方法种类代码实现和上一道题差不多只是换了内外层的遍历举例推导dp数组
这里有一个dp[i]INT_MAX-dp[i-nums[j]]操作因为测试数据比较大时累加结果可能超过了INT_MAX为了保证数据不溢出就需要判断dp[i]dp[i-nums[j]]INT_MAX是否成立而dp[i]dp[i-nums[j]]可能还是会溢出所以只能用减法写
代码实现
class Solution {
public:int combinationSum4(vectorint nums, int target) {vectorint dp(10010,0);dp[0]1;for(int i0;itarget;i){for(int j0;jnums.size();j){if(inums[j]dp[i]INT_MAX-dp[i-nums[j]])dp[i]dp[i-nums[j]];}}return dp[target];}
};
