配列が二つの場合の解法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/06/22 05:55 UTC 版)
「最長共通部分列問題」の記事における「配列が二つの場合の解法」の解説
最長共通部分列問題は、部分構造最適性を持つ。すなわち、この問題は、簡単な部分問題に分解することができ、それらはさらに簡単な部分問題に分解でき、そして最後には自明な問題に帰着される。またこの問題は、部分構造重複性を持つ。上位の部分問題を解く際には、しばしば下位の部分問題の解を再利用することになる。これら二つの特質を伴うこの問題は、動的計画法と呼ばれる手法で解決できる。動的計画法では、部分問題の解をその都度計算するのではなく、メモ化しておく。メモ化、すなわち、ひとつのレベルの部分問題の解をテーブルに格納して、次のレベルの部分問題が利用できるようにし、計算量を節約することが、この手続きには必要不可欠である(メモを取ることによく似ている所が、名前の由来である）。この解法を次に示す。
※この「配列が二つの場合の解法」の解説は、「最長共通部分列問題」の解説の一部です。
「配列が二つの場合の解法」を含む「最長共通部分列問題」の記事については、「最長共通部分列問題」の概要を参照ください。
ウィキペディア小見出し辞書の「配列が二つの場合の解法」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 配列が二つの場合の解法のページへのリンク
