DP F
from 動的計画法
DP_F
0で埋めた二次元配列を作るところをnp.zerosでやったが、生PythonだとTLEなので生リストにしてからPyPyした
chrはbuffer.readした時に文字が整数値になるので文字列に戻すためにやっている
pythondef solve(S, T):
sizeS = len(S)
sizeT = len(T)
m = [[0] * (sizeT + 1) for _i in range(sizeS + 1)]
for i in range(1, sizeS + 1):
for j in range(1, sizeT + 1):
m[i][j] = max(
m[i - 1][j],
m[i][j - 1],
m[i - 1][j - 1] + 1 if S[i - 1] == T[j - 1] else 0
)
result = []
i = sizeS
j = sizeT
while i > 0 and j > 0:
if m[i][j] == m[i - 1][j]:
i -= 1
elif m[i][j] == m[i][j - 1]:
j -= 1
else:
result.append(chr(S[i - 1]))
i -= 1
j -= 1
print("".join(reversed(result)))Related Pages
- →僕のatcoderの学び方(〜緑)×僕のatcoderの学び方(〜青)×arc106×気づきの言語化×結晶化×変形テクニックに名前をつける×行列の半分×二項定理×足し算の順序の変更×概念のハンドル×テストできるスニペットライブラリ×unionfind×mod_pでの組み合わせ×Educational DP Contest×動的計画法×atcoder_library_practice_contest×atcoder_library×帰着する力×帰着訓練→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]