白駿2293号:コイン1

5292 ワード
python ps DP テキストリンク
白駿2293号:コイン1

アイデア


コインa,b,cでK元を作ります.コインaを1元からK元だけ使用した場合は配列に記録されます(できれば1、もし不可能であれば0に充填されます).その後硬貨aとbが使用され、1元からK元の場合は配列に記録される.このときi(1<=i<=K)を作成する円の数は、硬貨aのみを使用してiを作成する円の数と、硬貨a,bを使用して(i-b)を作成する円の数との和である(i同様に、硬貨a,b,cを用いてi円を作製する数は、硬貨a,bを用いてi円を作製する数と、硬貨a,b,cを用いて(i−c)円を作製する数との総和である.
点火で表現すると.
d 2[i]=d 1[i]+d 2[i-v](d 1:前の配列、d 2:新しく作成された配列、v:現在選択されている硬貨の値)
画像で確認します.

(0円の作り方はコインを使わない方法です)

コード#コード#

N, K = map(int, input().split())
value = [int(input()) for _ in range(N)]

d1 = [1] + [0]*K
d2 = [1] + [0]*K

for i in range(1, K + 1):
    if i % value[0] == 0:
        d1[i] = 1

value.pop(0)

for v in value:
    for i in range(1, K + 1):
        if i < v:
            d2[i] = d1[i]
        else:
            d2[i] = d1[i] + d2[i - v]
    d1 = d2

print(d1[K])

おしゃべり


休暇から帰ってきて、隔離を加えて、一ヶ月が過ぎました.これからは努力して解決しなければなりません...
ConcurrentHashmap size(1.7 1.8)
Spring Springbootプロジェクトでquerydslを設定する