動的計画法の問題のまとめ[pythonのコード付き]

アルゴリズムとデータ構造
記事内に広告が含まれています。
スポンサーリンク

動的計画法の備忘録として、問題とその回答コードについてまとめておきます。

スポンサーリンク

注意

動的計画法が何かについての詳しい解説はしません。

詳細は以下のリンクなど他のサイトをご参照ください。

動的計画法(Dynamic Programming)入門 | アルゴリズムロジック
動的計画法とは 動的計画法(Dynamic Programming)とは、小さい部分問題を計算して記録しておき、より大きい問題を計算する際に利用する手法のことです。 以下のような...

AtCoder Beginner Contest 289 D

無限に続く階段があります。 一番下は 0 段目で、1 段のぼるごとに 1 段目、2 段目と続きます。

0 段目に階段登りロボットがいます。 階段登りロボットは、一回の動作で $A_1,A_2,…,A_N$段ぶん階段をのぼることができます。 つまり、階段登りロボットが i 段目にいるとき、一回動作をした後は $i+A_1$ 段目$i+A_2$ 段目、⋯、$i+A_N$ 段目のいずれかにいることができます。 それ以外の段数を一回の動作でのぼることはできません。 階段登りロボットは階段を下ることもできません。

階段の $B_1,B_2,…,B_N$ 段目にはモチが設置されています。 モチが設置されている段へのぼるとロボットは動けなくなり、他の段に移動することができなくなります。

階段登りロボットは階段のちょうど X 段目にのぼりたいです。 階段登りロボットが階段のちょうど X 段目にのぼることが可能か判定してください。

AtCoder Beginner Contest 289 D-Step Up Robot
  1. iBに含まれているかどうか
  2. i より前の段 i-A[0], i-A[1], ... , i-A[N]が到達可能かどうか

の2項目を確認すれば、i 段目に到達できるかどうかを計算できます。

N = int(input())
A = list(map(int, input().split()))
M = int(input())
B = set(map(int, input().split()))
X = int(input())

#動的計画法で解く
#1は到達可能な段とする
dp = [0]*(X+1)
dp[0] = 1

for x in range(X+1):
    #Bに含まれる場合は無視
    if x in B:
        continue
    #step
    for a in A:
        #0以上でかつBに含まれていない場合
        if x-a >= 0 and not x-a in B:
            dp[x] = max(dp[x], dp[x-a])


#print(dp)
if dp[-1]==1:
    print('Yes')
else:
    print('No')

注意点は、B をリストではなく集合set型にしている点です。

これは x in B の判定を$\mathcal{O}(1)$に高速化するための工夫で、リスト型にすると$\mathcal{O}(N)$ のため TLE となり不正解になります。

リストや集合の計算量については以下のサイトをご参照ください。

Pythonistaなら知っておきたい計算量のはなし - Qiita
最近久しぶりにアルゴリズムイントロダクションを読んでいるのですが、ふと「Python(CPython)のデータ構造に関する各操作の計算量ってどれくらいなのかな?」と気になったので調べてみました。以下のページを参考にしています: Pyt...

AtCoder Beginner Contest 286 D

高橋君は $N$ 種類の硬貨をそれぞれ何枚か持っており、 具体的には、1≤iN について $A_i$ 円硬貨を $B_i$ 枚持っています。

高橋君が現在持っている硬貨を用いて、(お釣りが出ないように)ちょうど $X$ 円を支払うことができるか判定してください。

AtCoder Beginner Contest 286 D-Money in Hand

この問題も動的計画法で解いていきます。

dp[i] = i 円 を作れる場合は True, 作れない場合は False

X 円を作れるかどうかについて、具体的な硬貨の枚数を知る必要はありません。したがって、$a$ 円を1枚持っている場合、$x$円を作れるかどうかは $x-a$円が作れるかどうかだけ分かればokです。

  • dp[x] = dp[x] | dp[x-a]

この手続きを$1,2,…,B_i$ 個の場合で計算します。

  • dp[x] = dp[x] | dp[x-a*2] (aが2枚の場合)
  • dp[x] = dp[x] | dp[x-a*3] (aが3枚の場合)
  • dp[x] = dp[x] | dp[x-a*n] (aがn枚の場合)

上記全体の手続きをすべての種類の硬貨で計算します。

N, X = map(int,input().split())
AB = []
dp = [False]*(X+1)
dp[0] = True
for _ in range(N):
    a,b = map(int, input().split())
    nx = [False]*(X+1)
    for i in range(X+1):
        #今まで見た硬貨で作れる金額の場合
        if dp[i]:
            for j in range(b+1):

                if i+a*j <= X:
                    nx[i+a*j] = True
    dp = nx
if dp[-1]:
    print('Yes')
else:
    print('No')

まとめ

動的計画法の問題について、今後も解いた問題をまとめていきたいと思います。