Open azl397985856 opened 3 weeks ago
经典完全背包问题 class Solution { public int change(int amount, int[] coins) { int[] f = new int[amount + 1]; f[0] = 1; for (int x : coins) { for (int c = x; c <= amount; c++) { f[c] += f[c - x]; } } return f[amount]; } }
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for i in range(1, amount + 1):
if coin <= i:
dp[i] += dp[i - coin]
return dp[amount]
var change = function (amount, coins) {
const dp = Array.from({ length: amount + 1 }).fill(0);
dp[0] = 1;
for (let coin of coins) {
for (let i = coin; i <= amount; i++) {
dp[i] += dp[i - coin];
}
}
return dp[amount];
};
时间复杂度:O(m*n) 空间复杂度:O(m)
/**
* @param {number} amount
* @param {number[]} coins
* @return {number}
*/
var change = function (amount, coins) {
const dp = new Array(amount + 1).fill(0);
dp[0] = 1;
for (const item of coins) {
for (let i = item; i <= amount; i++) {
dp[i] += dp[i - item];
}
}
return dp[amount]
};
class Solution { public int change(int amount, int[] coins) { int[] dp = new int[amount + 1]; dp[0] = 1; for (int coin : coins) { for (int i = coin; i <= amount; i++) { dp[i] += dp[i - coin]; } } return dp[amount]; } }
class Solution: def change(self, amount: int, coins: list[int]) -> int: dp = [0] * (amount + 1) dp[0] = 1 for coin in coins: for i in range(coin, amount + 1): dp[i] += dp[i - coin] return dp[amount]
518. 零钱兑换 II
入选理由
暂无
题目地址
https://leetcode-cn.com/problems/coin-change-2/
前置知识
暂无
题目描述
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1: