algorithm - 再帰的な最長増加部分列のメモ化

Question

私は、最長増加部分列のための単純な次の再帰的解決策を思いついた。しかし、この再帰的なソリューションにメモ化を含めるのを手伝ってもらえますか。

public int findLIS(int a[], int maxSoFar, int item, int count) {

        if(item == a.length) {
            return count;
        }
        int length1 = findLIS(a,maxSoFar, item+1, count);
        int length2 = 0;
        if(a[item] > maxSoFar) {

            length2 = findLIS(a, a[item], item+1, count + 1);
        }
        return Math.max(length1, length2);
}

PS：これは宿題の質問ではなく、私の興味の対象です。

Answer 1

を使用しMap<Pair<Integer,Integer>,Integer>、メソッドの先頭に次を追加します。

Integer cache = map.get(new Pair<Integer,Integer>(maxSoFar,item));
if (cache != null) return cache;

あなたが何かするたびにreturn- 必ず(maxSoFar,item)=returnValue地図に書き込んでください。

アイデアは、計算のどこにいるかを表すペアの間で、この状態で見つかった最大値にマッピングして、再計算を避けることです。

---

Javaらしいので、 apache commons Pairをインターフェースとして使えPairます。