递归的记忆递增最长递增子序列

我想出了一个简单的递归解决方案，用于递增最长的子序列。但是，您能否帮助将记忆纳入此递归解决方案？递归的记忆递增最长递增子序列

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

来源

2012-12-08 coder000001

这是什么语言？ – irrelephant

爪哇，但你可以很容易地转换为你最喜欢的语言。我可以为你做，如果你想 – coder000001

使用Map<Pair<Integer,Integer>,Integer>，在Add方法的开头：

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

每次return任何东西 - 请务必写(maxSoFar,item)=returnValue地图。

这个想法是将代表您在计算中的位置的对映射到为此状态找到的最大值，以避免重新计算它。

似乎Java，所以你可以使用apache commons Pair为您Pair接口。

来源

2012-12-08 21:17:30 amit

Thanks.Before在这里发表之前，我迅速检查了一系列{10,22,9,33,21,50,41,60,80};和备忘录= new int [10] [81]; 但是，它并没有为我工作。我也会检查你的解决方案。 – coder000001

@ coder000001：它相当于地图解决方案。请发布您使用的代码，可能有一个错误 – amit

谢谢，它的工作原理。 – coder000001

递归的记忆递增最长递增子序列

回答

相关问题