Dynamic programming配列解析の出発点は、ダイナミックプログラミング（DP: dynamic programming）法による２つの配列アライメントを理解することである。いま２つの文字列が与えられたときに、適当な場所にギャップを入れてずらすことにより、両者で対応する文字の一致数が最大になるような並べ方を探してみよう。上の図に２つの文字列ＡＩＭＳとＡＭＯＳを例として、ダイナミックプログラミング法の原理が示されている。この場合 ＡＩＭ−Ｓ Ａ−ＭＯＳ のように−で示した位置にギャップを入れて並べると３つの文字が一致する。これが最大の一致数に対応したアライメント、すなわち最適アライメント（optimal alignment）で、この問題の解となる。アライメントの問題とは結局、ある評価関数（この例では文字の一致数）を最適にする最適化問題に帰着するのである。 ダイナミックプログラミング法による解法は、比較する配列を横方向
