動的計画法を使用した最長増加部分列

1. 序章

このチュートリアルでは、最長増加部分列（LIS）の問題について説明します。

ソートされていない要素の配列が与えられた場合、アイデアは、要素が昇順（最低から最高）にある最長のサブシーケンスの長さを見つけることです。

サブシーケンスの要素は、必ずしも初期配列の連続した位置に表示される必要はなく、LISのソリューションは常に一意であるとは限りません。

要素{-3、10、5、12、15}について、次の増加するサブシーケンスを識別します。

リストからわかるように、最長増加部分列は{-3、5、12、15}で長さは4です。ただし、{-3、10、12、15}も同じ長さの最長増加部分列であるため、これが唯一の解決策ではありません。

LISの単純な実装は、最初に、指定された配列のすべての可能なサブシーケンスを検討することです。次に、増加しているすべてのサブシーケンスをチェックし、その長さを保存します。このプロセスを実行した後、検出した最長のものの長さを返すことができます。

サイズnの配列には2^ n サブセットが含まれているため、このアプローチの複雑さは O（2 ^ n）です。たとえば、 [1,2,3] には、サブセット {}、{1}、{2}、{3}、{1,2}、{1,3}、{2、 3}、{1,2,3}。

動的計画法のアプローチでパフォーマンスを向上させることができます。動的計画法は、問題を複数の小さなサブ問題に分解し、それらのソリューションを使用して大きな問題を構築する手法であることを思い出してください。

特にこの場合、集計を使用できます。

最初に、配列 arr[]のすべてのインデックスiのLISが1であると想定します。
配列を左から右に解析して、インデックスiの各要素を確認します。
すべての要素について j まで私（どこ j ）、インデックスの要素の場合私インデックスの要素よりも大きい j と lis [i] <= lis [j] それから lis [i] = lis [j] + 1
すべてのLIS値のすべての最大値を選択します

このアルゴリズムの背後にある直感は、 i-1、が最終的に最長のものに達するまで、以前のすべての数値を調べることにより、インデックスiの数値の増加するすべてのサブシーケンスを見つけることができるということです。

これの複雑さはO（n ^ 2）です。これは、外側のループで配列を1回トラバースし、 O（n）の複雑さを生成し、次にすべての要素[X163X ] i 、1からiまでのすべての要素jの線形検索を行います。

このチュートリアルでは、最長増加部分列問題を示しました。

また、単純な実装と動的計画法を使用した実装についても見てきました。