1. 目的

初中級者が解くべき過去問精選 100 問をPythonで解きます。
すべて解き終わるころに水色になっていることが目標です。

本記事は「034 - 038 動的計画法：ナップザック DP」です。

2. 総括

DP はかなり苦労しました。BFS、DFSもかなり苦労しましたが、それ以上にDPが少しだけわかるまでかなり悩みました。
やったことは、BFS、DFSのときと同じで、解説をよみつつ、ACの回答例を理解できるまで1行ずつデバックで追っていくのみです。
また、精選100問のDPが最初まったくできなかったので、先にTypical DP ContestをA~Lまで解いてから（というか回答例を見ながら理解した）着手しました。
すると、少しだけ解けるるようになっていました。

3. 本編

034 - 038 動的計画法：ナップザック DP基本

034. ALDS_10_A - フィボナッチ数

回答


n = int(input())
dp = [0] * (n + 1)

dp[0] = 1
dp[1] = 1

for i in range(2, n+1):
    dp[i] = dp[i - 1] + dp[i -2]

print(dp[n])

下記のように再帰で書くとTLEで通りませんので``DP```で解く必要がある、ということがわかる問題です。


# これではTLE
num = int(input())

def fib(num):
    if num == 0:
        return 1
    if num == 1:
        return 1

    return fib(num - 1) + fib(num - 2)

print(fib(num))

035. DPL_1_B - 0,1ナップザック問題

回答


N, W = map(int, input().split()) # N個の品物、Wが重さの容量
p = [(0, 0)] + [tuple(map(int, input().split())) for _ in range(N)] # 品物-> (価値, 重さ)
dp = [[0] * (W+1) for _ in range(N+1)] # 縦が品物の番号、横が現在の容量、dpの中身が最大の価値とする

for i in range(1, N+1):
    for j in range(1, W+1):
        
        if j-p[i][1] >= 0:
            dp[i][j] = max(dp[i-1][j],
                           dp[i-1][j-p[i][1]] + p[i][0])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[N][W])

典型中の典型です。
1次元dpで書く方法もあるようですが、僕はこのほうが書きやすいです。

036. DPL_1_C - ナップザック問題

回答


N, W = map(int, input().split()) # Nは品物の種類、Wは上限の重さ
p = [(0, 0)] + [tuple(map(int, input().split())) for _ in range(N)] # (価値, 重さ)
dp = [[0] * (W+1) for _ in range(N+1)]

for i in range(1, N+1):
    for j in range(1, W+1):

        if j-p[i][1] >= 0:
            dp[i][j] = max(dp[i-1][j],
                           dp[i][j-p[i][1]] + p[i][0])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[N][W])

問題35との違いは、同種類の製品を重複して選べる点ですので、コードもその部分だけ修正してやります。
具体的には、


dp[i][j] = max(dp[i-1][j],
               dp[i-1][j-p[i][1]] + p[i][0])

と


dp[i][j] = max(dp[i-1][j],
               dp[i][j-p[i][1]] + p[i][0])

で、maxの中身が違います。問題35は「添え字iの一つ前から重さを引いて自分の価値を足す」という形でしたが、問題36は「自分の重さを引いて自分の価値を足す」です。

037. DPL_1_A - コイン問題

回答


INF = float('inf')
n, m = map(int, input().split())
coins = [0] + list(map(int, input().split()))
dp = [[INF] * (n+1) for _ in range(m+1)]

dp[0][0] = 0

for i in range(1, m+1):
    for j in range(n+1):
        
        if j-coins[i] >= 0:
            dp[i][j] = min(dp[i-1][j-coins[i]] + 1,
                           dp[i][j-coins[i]] + 1,
                           dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[m][n])

コイン問題も典型で、ナップサックと考え方はほぼ同じです。

038. ALDS_10_C - 最長共通部分列

回答


# これだと通るけど好きじゃない。
def main(A, B):
    dp = [0] * (len(B)+1)

    for a in A:
        before = dp[:]
        for j in range(1, len(B)+1):
            
            if a == B[j-1]:
                dp[j] = before[j-1] + 1
            elif dp[j] < dp[j-1]:
                dp[j] = dp[j-1]
                            
    return dp[-1]


if __name__ == "__main__":
    q = int(input())
    for _ in range(q):
        A = list(input())
        B = list(input())
        print(main(A, B))

問題34~37と同じように書くと下記のようになります。僕はこの書き方が一番わかりやすいし、最長共通部分列の復元も行いやすいので好きです。
しかしシステム上は下記のように書くとTLEとなってしまうので、いろいろ工夫して高速化をしたのが上記の回答です。


# これだとTLE。復元はやりやすい。
q = int(input())

answer_list = []
for _ in range(q):
    A = [''] + list(input())
    B = [''] + list(input())
    dp = [[0] * (len(B)) for _ in range(len(A))]

    for i in range(1, len(A)):
        for j in range(1, len(B)):
            
            if A[i] == B[j]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i][j-1],
                               dp[i-1][j])

    print(dp[len(A)-1][len(B)-1])

特に文字Aについて、for i in range(1, len(A)):で回した場合にくらべfor a in A:でまわしたほうが早いようです。やはり、リストに添え字でアクセスするのが結構遅いのかもしれません。