记忆化递归最长递增子 [英] memoization for recursive Longest Increasing subsequence

问题描述

我想出了以下简单的最长的递归解决方案增加子序列。 但是，你能不能帮到包括记忆化到这个递归解决方案。

I came up with simple following recursive solution for Longest increasing sub-sequence. But, Can you help to include memoization into this recursive solution.

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：这不是一个家庭作业的问题，它更多的是我的兴趣

PS: This not a homework question, it is more of my interest.

推荐答案

使用地图＆LT;对＆LT;整数，整数GT;，整数GT; ，并在该初方法Add：

Use a Map<Pair<Integer,Integer>,Integer>, and at the beginning of the method add:

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

每次返回任何事情 - 请务必写（maxSoFar，项目）=的returnValue 到地图中。

Each time you return anything - make sure to write (maxSoFar,item)=returnValue to the map.

我们的想法是，稀土present你在哪里，在计算对之间的映射 - 要找到这种状态的最大值，以避免重新计算它

The idea is to map between the pair that represent where you are in the calculation - to the maximal value found for this state, to avoid recalculating it.

看来java的，所以你可以使用的阿帕奇公地对的为你的对接口。

It seems java, so you can use apache commons Pair as your Pair interface.

这篇关于记忆化递归最长递增子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！