Đề bài · thuật toán trung bình Python ·
Ways to make change
Count the ways to make amount from coins of the given distinct positive denominations, each usable any number of times. Order doesn't matter (1+2 and 2+1 are the same way). Return the count modulo 1,000,000,007. There is exactly one way to make 0. Up to 60 denominations and amounts up to 30,000.
Khai báo hàm
def coin_ways(coins: list[int], amount: int) -> int:Ví dụ
coin_ways([1, 2, 5], 5) # -> 4
coin_ways([2], 3) # -> 0
coin_ways([10], 10) # -> 1Kèm theo 7 test ẩn và 1 test dữ liệu lớn có giới hạn thời gian; dữ liệu đầu vào không được hiển thị. Đề bài được giao cho các mô hình bằng tiếng Anh.
#1Mistral Devstral 2 2512đã giải · 11/11 testtrả lời trong 906 ms · thời gian chạy 345 ms · $0.0003 ✓ coin_ways([1, 2, 5], 5)kỳ vọng 4 2 ms ✓ coin_ways([2], 3)kỳ vọng 0 <1 ms ✓ coin_ways([10], 10)kỳ vọng 1 <1 ms ✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 15 ms⏱ 322 msCode
def coin_ways(coins: list[int], amount: int) -> int: MOD = 10**9 + 7 dp = [0] * (amount + 1) dp[0] = 1 for coin in coins: for i in range(coin, amount + 1): dp[i] = (dp[i] + dp[i - coin]) % MOD return dp[amount]#1Qwen3 Coder Nextđã giải · 11/11 testtrả lời trong 2.8 giây · thời gian chạy 352 ms · $0.0002 ✓ coin_ways([1, 2, 5], 5)kỳ vọng 4 <1 ms ✓ coin_ways([2], 3)kỳ vọng 0 <1 ms ✓ coin_ways([10], 10)kỳ vọng 1 2 ms ✓ 1 ms✓ <1 ms✓ 2 ms✓ 3 ms✓ <1 ms✓ <1 ms✓ 14 ms⏱ 327 msCode
def coin_ways(coins: list[int], amount: int) -> int: MOD = 1000000007 # dp[i] = number of ways to make amount i dp = [0] * (amount + 1) dp[0] = 1 # One way to make 0: use no coins # For each coin, update dp array for all amounts >= coin for coin in coins: for i in range(coin, amount + 1): dp[i] = (dp[i] + dp[i - coin]) % MOD return dp[amount]#1SpaceXAI Grok Build 0.1đã giải · 11/11 testtrả lời trong 5.4 giây · thời gian chạy 354 ms · $0.0022 ✓ coin_ways([1, 2, 5], 5)kỳ vọng 4 <1 ms ✓ coin_ways([2], 3)kỳ vọng 0 <1 ms ✓ coin_ways([10], 10)kỳ vọng 1 <1 ms ✓ <1 ms✓ <1 ms✓ 1 ms✓ <1 ms✓ <1 ms✓ <1 ms✓ 14 ms⏱ 334 msCode
def coin_ways(coins: list[int], amount: int) -> int: MOD = 1000000007 dp = [0] * (amount + 1) dp[0] = 1 for coin in coins: for x in range(coin, amount + 1): dp[x] = (dp[x] + dp[x - coin]) % MOD return dp[amount]#1Anthropic Claude Haiku 5.5đã giải · 11/11 testtrả lời trong 1.7 giây · thời gian chạy 355 ms · $0.0002 ✓ coin_ways([1, 2, 5], 5)kỳ vọng 4 <1 ms ✓ coin_ways([2], 3)kỳ vọng 0 2 ms ✓ coin_ways([10], 10)kỳ vọng 1 <1 ms ✓ <1 ms✓ <1 ms✓ 1 ms✓ 1 ms✓ 1 ms✓ 1 ms✓ 15 ms⏱ 330 msCode
def coin_ways(coins: list[int], amount: int) -> int: MOD = 1_000_000_007 if amount < 0: return 0 dp = [0] * (amount + 1) dp[0] = 1 for c in coins: if c <= 0 or c > amount: continue for a in range(c, amount + 1): dp[a] = (dp[a] + dp[a - c]) % MOD return dp[amount] % MOD
Chi phí token: $0.0028 · Cách thức thi đấu và tính điểm →