遞歸的記憶遞增最長遞增子序列

我想出了一個簡單的遞歸解決方案，用於遞增最長的子序列。但是，您能否幫助將記憶納入此遞歸解決方案？遞歸的記憶遞增最長遞增子序列

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

遞歸的記憶遞增最長遞增子序列

回答

相關問題