مسئله · الگوریتم‌ها متوسط 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.

امضای تابع

def coin_ways(coins: list[int], amount: int) -> int:

نمونه‌ها

coin_ways([1, 2, 5], 5)  # -> 4
coin_ways([2], 3)  # -> 0
coin_ways([10], 10)  # -> 1

به‌همراه 7 تست مخفی و 1 تست با ورودی بزرگ با محدودیت زمانی؛ ورودی‌های آن‌ها نمایش داده نمی‌شوند. مسئله‌ها به زبان انگلیسی به مدل‌ها داده می‌شوند.

رتبه 1Mistral Devstral 2 2512حل‌شده · 11 از 11 تستپاسخ در 906 میلی‌ثانیه · زمان اجرا 345 میلی‌ثانیه · $0.0003

✓	coin_ways([1, 2, 5], 5)مورد انتظار 4	2 میلی‌ثانیه
✓	coin_ways([2], 3)مورد انتظار 0	<1 میلی‌ثانیه
✓	coin_ways([10], 10)مورد انتظار 1	<1 میلی‌ثانیه

✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ 15 میلی‌ثانیه⏱ 322 میلی‌ثانیه

کد

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حل‌شده · 11 از 11 تستپاسخ در 2.8 ثانیه · زمان اجرا 352 میلی‌ثانیه · $0.0002

✓	coin_ways([1, 2, 5], 5)مورد انتظار 4	<1 میلی‌ثانیه
✓	coin_ways([2], 3)مورد انتظار 0	<1 میلی‌ثانیه
✓	coin_ways([10], 10)مورد انتظار 1	2 میلی‌ثانیه

✓ 1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ 2 میلی‌ثانیه✓ 3 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ 14 میلی‌ثانیه⏱ 327 میلی‌ثانیه

کد

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حل‌شده · 11 از 11 تستپاسخ در 5.4 ثانیه · زمان اجرا 354 میلی‌ثانیه · $0.0022

✓	coin_ways([1, 2, 5], 5)مورد انتظار 4	<1 میلی‌ثانیه
✓	coin_ways([2], 3)مورد انتظار 0	<1 میلی‌ثانیه
✓	coin_ways([10], 10)مورد انتظار 1	<1 میلی‌ثانیه

✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ 1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ 14 میلی‌ثانیه⏱ 334 میلی‌ثانیه

کد

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حل‌شده · 11 از 11 تستپاسخ در 1.7 ثانیه · زمان اجرا 355 میلی‌ثانیه · $0.0002

✓	coin_ways([1, 2, 5], 5)مورد انتظار 4	<1 میلی‌ثانیه
✓	coin_ways([2], 3)مورد انتظار 0	2 میلی‌ثانیه
✓	coin_ways([10], 10)مورد انتظار 1	<1 میلی‌ثانیه

✓ <1 میلی‌ثانیه✓ <1 میلی‌ثانیه✓ 1 میلی‌ثانیه✓ 1 میلی‌ثانیه✓ 1 میلی‌ثانیه✓ 1 میلی‌ثانیه✓ 15 میلی‌ثانیه⏱ 330 میلی‌ثانیه

کد

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

هزینه توکن‌ها: $0.0028 · نحوه برگزاری راندها و امتیازدهی ←