Cette variante contrainte du problème combinatoire classique a une solution récursive raisonnablement simple. Dans le cas de base, le nombre de chemins allant de l'origine (0, 0) à elle-même est égal à un pour le chemin vide (notez la différence cruciale entre un chemin vide qui existe et un chemin inexistant!) Si le point (x, y) figure dans la liste tabu, le nombre de chemins de ce point à l'origine est égal à zéro. Sinon, le nombre de chemins du point à l'origine est égal à la somme des chemins des deux voisins (x-1, y) et (x, y-1). Cependant, cette simple récursion se ramifie en un nombre exponentiel de possibilités et peut donc être beaucoup trop lente à exécuter. Par conséquent, vous devriez soit mémoriser la récursion à l'aide de lru_cache, ou mieux encore...

N'utilisez pas du tout la récursivité mais construisez une liste à deux dimensions dont les entrées sont les solutions individuelles des sous-problèmes. Remplissez les valeurs...