网站免费推广方式,办公空间设计平面图,seo页面优化平台,哪些网站可以做企业推广代码随想录算法训练营第7周#xff08;C语言#xff09;|Day41#xff08;动态规划#xff09;
Day44、动态规划#xff08;包含题目 ● 518. 零钱兑换 II ● 377. 组合总和 Ⅳ #xff09;
518. 零钱兑换 II
题目描述
给定不同面额的硬币和一个总金额。写出函数来计… 代码随想录算法训练营第7周C语言|Day41动态规划
Day44、动态规划包含题目 ● 518. 零钱兑换 II ● 377. 组合总和 Ⅳ
518. 零钱兑换 II
题目描述
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
题目解答
int change(int amount, int* coins, int coinsSize) {int dp[amount1];for(int i0;iamount;i){dp[i]0;}dp[0]1;for(int i0;icoinsSize;i){for(int jcoins[i];jamount;j){dp[j]dp[j-coins[i]];}}return dp[amount];
}
题目总结
完全背包组合问题 先物品后背包。
377. 组合总和 Ⅳ
题目描述
给你一个由 不同 整数组成的数组 nums 和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目解答
int combinationSum4(int* nums, int numsSize, int target) {int dp[target1];for(int i0;itarget;i){dp[i]0;}//memset(dp, 0 , sizeof(int)*(target1));dp[0]1;for(int i1;itarget;i){for(int j0;jnumsSize;j){if(nums[j]i dp[i]INT_MAX-dp[i-nums[j]]){dp[i]dp[i-nums[j]];}}}return dp[target];
}题目总结
完全背包排列问题先背包后物品。
