コイン枚

質問する

白駿9084号硬貨

に答える

dp基本問題.疲れて頭がもたもたする
必要に応じてリストdpの金額mを作成し、全てを0にリセットする.
リスト要素はi-c(동전의 금액)に近いので、1はdp[0]に容易に格納される.
次に、コイン1枚あたりdpの価格を更新します.

T = int(sys.stdin.readline())
for _ in range(T):
    n = int(sys.stdin.readline())
    coin = list(map(int, sys.stdin.readline().split()))
    m = int(sys.stdin.readline())

    dp = [0] * (m+1)
    dp[0] = 1
    for c in coin:
        for i in range(c, m+1):
            dp[i] += dp[i-c]
    print(dp[m])