Article très intéressant sur le vocabulaire que je vais essayé de résumer.

La Programmation Dynamique (DP)

La programmation dynamique consiste à réorganiser un arbre d'appels récursifs en graphe orienté convergent, où des embranchements impliquant la même exécution vont voir leurs résultats mémorisés afin de ne pas être recalculés.

Typiquement pour le calcul d'une suite de Fibonacci nous avons cet arbre avant :

Transformé en ce graphe après (ou le résultat de **fib(1) a été mémorisé) :

La memoization

La mémoïsation en français est une technique qui consiste à mettre en cache les valeurs déjà calculée.

L'exemple de l'article est le suivant :

fun square(x) {
    return x * x
}

fun square_memoized(x) {
    if (mem[x] is not set) {
        mem[x] = x * x
    }
    return mem[x]
}

La tabulation

Cette technique ressemble un peu à la memoization mais consiste à remplir le cache systématiquement jusqu'au moment où l'on trouve la bonne valeur, alors que la memoization va se concentrer sur la valeur à retourner directement.

L'exemple donné est le suivant :

fun fib_tab(n) {
    mem[0] = 0
    mem[1] = 1
    for i = 2...n
        mem[i] = mem[i-2] + mem[i-1]
    return mem[n]
}

Donc l'exécution réelle donne ceci :

mem[0] = 0
mem[1] = 1
mem[2] = mem[0] + mem[1]
mem[3] = mem[1] + mem[2]
mem[4] = mem[2] + mem[3]

On voit bien que le cache est surutilisé dans le cadre de la tabulation puisque chaque valeur suivante s'appuie sur la précédente forcément cachée. De facto, la tabulation consomme plus de mémoire mais garantie un accès instantané à la valeur dès la seconde utilisation, à l'image des caches gloutons finalement ("goutons" au sens algorithmes gloutons du terme).