En considérant l'implémentation ci-dessus, voici l'arbre de récurrence pour un tableau de taille 4. lis nous donne la longueur de LIS pour arr [].

Nous pouvons voir qu'il y a beaucoup de sous-problèmes qui sont résolus encore et encore. Ce problème a donc une propriété de sous-structure se chevauchant et le recalcul des mêmes sous-problèmes peut être évité en utilisant la mémorisation ou la tabulation. Vous trouverez ci-dessous une implémentation sous forme de tableau pour le problème LIS utilisant la programmation dynamique.

Fonction LIS_P (arr :tableau d’entier, n :entier) :entier

Var Lis :tableau [1..n] d’entier

Debut

Lis[0]ß1 ;

Pour iß 1 à n faire debut

Lis[i]ß1 ;

Pour jß 0 à i faire debut

Si(arr[i]>arr[j] et lis[i]<(lis[j]+1)) alors lis[i]ß lis[j]+1 ;

Fin pour boucle j

Fin pour boucle i

Retourner max (lis[])

Fin fonction LIS

La complexité :

Notez que la complexité temporelle de la solution de programmation dynamique (DP) ci-dessus est O (n ^ 2)