nishiohirokazu https://blog.hatena.ne.jp/nishiohirokazu/ 西尾泰和のはてなダイアリー https://nishiohirokazu.hatenadiary.org/ 前に86チャットで誰かがdiffを作ろうとしていて、長さ N, M の文字列に対して素朴に N * M の配列を確保していたせいで大きなサイズの入力でメモリを食い過ぎて破綻していたときに「動的計画法で端から埋めていくんだから、直前の１列だけ取っておくだけでいいでしょ」「いや、後でパスを求めないと行けないから全部持つ必要があるんだ！」「ないよ！パスの根元だけ参照で持っておけばいらないパスはGCで消えるでしょ！」という話をしたんだが、今ちょっと自分でも必要になったので作ってみた。うん、思った通りに動くな。テストケースに書いてあるけど、実行すると下のような入出力になる。 >>> test("1", … 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fnishiohirokazu.hatenadiary.org%2Fentry%2F20080628%2F1214631753" title="Needleman-Wunsch algorithmを実装した - 西尾泰和のはてなダイアリー" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2008-06-28 14:42:33 rich https://nishiohirokazu.hatenadiary.org/entry/20080628/1214631753 1.0 100%