我想出了以下简单的最长的递归解决方案增加子序列。 但是,你能不能帮到包括记忆化到这个递归解决方案。
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.
使用地图<对<整数,整数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.