施工企业资质标准,青岛谷歌优化公司,云主机是不是可以搭建无数个网站,制作广告图片的软件app题目 给你一个整数数组 coins 表示不同面额的硬币#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带符号整数。…题目 给你一个整数数组 coins 表示不同面额的硬币另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带符号整数。 示例 1 输入amount 5, coins [1, 2, 5] 输出4 解释有四种方式可以凑成总金额 55 5221 52111 511111 示例 2 输入amount 3, coins [2] 输出0 解释只用面额 2 的硬币不能凑成总金额 3 。 示例 3 输入amount 10, coins [10] 输出1
解题思路 这是一个完全背包问题用dp[j]表示凑齐金额为j的方案数对于当前的金额jdp[j]可以由两部分组成一部分是不选取当前硬币coins[i]那么dp[j]的值就等于之前的dp[j]另一部分是选取当前硬币coins[i]那么dp[j]的值就等于dp[j - coins[i]]表示已经使用了一个coins[i]还需要凑齐金额j - coins[i]。初始化dp[0]1. 最后返回dp[amount]即为结果。
代码实现
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];}
};
