memoization pour la sous-séquence croissante la plus longue récursive

Question

Je suis venu avec la solution récursive simple suivante pour la plus longue sous-séquence croissante. Mais, Pouvez-vous aider à inclure memoization dans cette solution récursive.

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: Ce n'est pas une question de devoirs, c'est plus de mon intérêt.

Answer 1

Utilisez un Map<Pair<Integer,Integer>,Integer> et au début de la méthode ajouter:

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

Chaque fois que vous return quoi que ce soit - assurez-vous d'écrire (maxSoFar,item)=returnValue à la carte.

L'idée est de mapper entre la paire qui représente où vous êtes dans le calcul - à la valeur maximale trouvée pour cet état, pour éviter de le recalculer.

---

Il semble java, vous pouvez utiliser apache commons Pair comme interface Pair.