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

使用 a 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接口。