結果

問題 No.225 文字列変更(medium)
ユーザー konsin_tokagekonsin_tokage
提出日時 2018-03-28 10:19:55
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
RE  
実行時間 -
コード長 426 bytes
コンパイル時間 71 ms
コンパイル使用メモリ 10,780 KB
実行使用メモリ 163,952 KB
最終ジャッジ日時 2023-09-07 19:18:55
合計ジャッジ時間 26,590 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 AC 16 ms
7,796 KB
testcase_03 AC 16 ms
7,788 KB
testcase_04 AC 18 ms
7,840 KB
testcase_05 AC 17 ms
7,844 KB
testcase_06 AC 17 ms
7,832 KB
testcase_07 AC 16 ms
7,836 KB
testcase_08 AC 17 ms
7,792 KB
testcase_09 AC 17 ms
7,828 KB
testcase_10 AC 17 ms
7,820 KB
testcase_11 AC 16 ms
7,940 KB
testcase_12 AC 2,483 ms
153,116 KB
testcase_13 AC 2,701 ms
163,952 KB
testcase_14 AC 2,627 ms
160,388 KB
testcase_15 AC 2,486 ms
147,480 KB
testcase_16 AC 2,584 ms
156,688 KB
testcase_17 AC 2,500 ms
148,012 KB
testcase_18 AC 2,429 ms
149,720 KB
testcase_19 AC 2,523 ms
156,436 KB
testcase_20 AC 2,392 ms
151,068 KB
testcase_21 AC 2,502 ms
155,300 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, m = map(int, input().split())
s = input()
t = input()
memo = {}
def dfs(i, j):
    if i == n and j == m:
        return 0
    if (i,j) in memo:
        return memo[i,j]
    res = 1001
    if i < n and j < m:
        res = min(res, int(s[i]!=t[j]) + dfs(i+1, j+1))
    if i < n:
        res = min(res, 1 + dfs(i+1, j))
    if j < m:
        res = min(res, 1 + dfs(i, j+1))
    memo[i,j] = res
    return res
print(dfs(0, 0))
0