動的プログラミング-効率的な通貨構成

4911 ワード
algorithm これがコードテストです ダイナミックプログラミング テキストリンク
ダイナミックプログラミング技術
解決した問題の一部の答えをメモリに記録し、一度に計算した問題の再計算を回避する解決方法.
タワー
再帰関数を使用して小さな問題を呼び出し、大きな問題を解決します.
昇降方式
繰り返し文を使用して、まず小さな問題を解決し、解決した小さな問題を集中して大きな問題を解決します.

に質問


N種類の通貨があります.これらの通貨の個数を最小限に抑え、その価値の和をM元にしようとした.この場合、1つの通貨ごとにいくつか使用することができ、使用する通貨の構成は同じであるが、順序が異なる場合、同じ場合に区別することができる.
不可能な場合は-1を出力します.

入力例1


2 15
2
3

出力例1


5

入力例2


2 15
2
3

出力例2


5

💻 コード#コード#

N, M = map(int, input().split())

d = [-1] * 10001

money = []

for i in range(N):
    x = int(input())
    money.append(x)
    d[x] = 1
    
for i in range(1, M):
    if d[i] != -1:
        for j in money:
            if d[i + j] == -1:
                d[i + j] = d[i] + 1
            else:
                d[i + j] = min(d[i + j], d[i] + 1)

print(d[M])

デザイン


インベントリdには、インデックス値を作成できる通貨の数が格納される.初期化は-1であり、通貨を入力するたびにdの1に入れ、通貨リストに入れます.
リストdを巡回しながら、少なくとも−1または入力可能な通貨にすることができる数を格納する.

📝 整理する


これはいろいろな方法で解決した問題です.
以前は初めて思いついた方法で解けなくてもずっと掴んでいましたが、今回は解けない方法で、別の方法を探すことができます.
CTFライトアップ:Picoctf
Centos 7がDjangoサービスをオープンしてもリモートアクセスができないという問題を解決