完全背包求方案数，LeetCode 518. 零钱兑换 II

本文主要是介绍完全背包求方案数，LeetCode 518. 零钱兑换 II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目

1、题目描述

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。 

题目数据保证结果符合 32 位带符号整数。

2、接口描述

​

class Solution {
public:int change(int amount, vector<int>& coins) {}
};

3、原题链接

518. 零钱兑换 II - 力扣（LeetCode）

---

二、解题报告

1、思路分析

求方案数的完全背包

定义状态f[i][j]为前i个物品装满容量为j的背包的方案数

那么f[i][j] = f[i][j] + f[i - 1][j - c[i]]

2、复杂度

时间复杂度：O(nm) 空间复杂度：O(nm)

3、代码详解

​cpp

class Solution {
public:int change(int amount, vector<int>& coins) {vector<int> dp(amount + 1);dp[0] = 1;for(auto x : coins){for(int j = x; j <= amount; j++)dp[j] += dp[j - x];}return dp[amount];}
};

python3

class Solution:def change(self, amount: int, coins: List[int]) -> int:dp = [0] * (amount + 1)dp[0] = 1for x in coins:for j in range(x, amount + 1):dp[j] += dp[j - x]return dp[amount]

这篇关于完全背包求方案数，LeetCode 518. 零钱兑换 II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---