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:でまわしたほうが早いようです。やはり、リストに添え字でアクセスするのが結構遅いのかもしれません。