En fait, ça rentre assez mal dans le schéma classique de la programmation dynamique. Il est plus simple d'énumérer les expressions comme tu le fais, tandis que si on appliquait bêtement le schéma classique, on essaierait de dire "je veux les solutions pour 4 huit, donc je vais d'abord chercher celles avec 1, 2 ou 3 huit".
Construire la liste des expressions est un processus récursif, je ne comprend pas bien comment tu es arrivé à en faire une boucle, qui te fera revenir plusieurs fois sur la même expression.
Une première versionLe tableau est assez creux, et itérer dessus est assez inefficace. C'est un argument supplémentaire en faveur de la récursivité. Mais au delà de ça, il reste des boucles dans le programme précédent, qui vont itérer sur beaucoup de vide. J'ai autorisé les valeurs à monter à 256 et il y a beaucoup de valeur inatteignables entre 1 et 256. Du coup, plutôt que d'itérer sur le tableau pour trouver des expressions déjà construites, je vais les stocker dans une liste et itérer la liste. En prime, ça simplifie un poil le programme.
Une seconde versionSur ma machine, la première version termine en 4ms et la seconde en 2ms. On peut optimiser en utilisant ta remarque, (sqrt(8*8) = 8) ce qui réduirait le nombre d'expressions à stocker, mais requiert un chaînage un peu plus élaboré que les listes ocaml.
