2020-01-01から1年間の記事一覧
背景 動的計画法を実行する際、計算した部分問題の解をテーブルに書き込んでいくわけだが、問題によっては、テーブルの全体を最後まで持っておく必要がないこともある。 例として、2つの文字列のレーベンシュタイン距離を求める問題を考える。二つの文字列の…
背景 動的計画法を実行する際、計算した部分問題の解をテーブルに書き込んでいくわけだが、問題によっては、テーブルの全体を最後まで持っておく必要がないこともある。 例として、2つの文字列のレーベンシュタイン距離を求める問題を考える。二つの文字列の…