La pyramide de nombres

La pyramide de nombres.

On descend du sommet d'une pyramide de nombres jusqu'à sa base ; à chaque étage, on passe à l'un des deux nombres situés juste en dessous (à gauche ou à droite). On cherche la somme maximale des nombres rencontrés. La pyramide est représentée par une liste de lignes :

pyramide = [[3],
            [7, 4],
            [2, 4, 6],
            [8, 5, 9, 3]]

Depuis la case pyramide[i][j], on peut descendre en pyramide[i+1][j] ou en pyramide[i+1][j+1].

• Combien de chemins une pyramide de $n$ étages compte-t-elle ? Pourquoi l'essai de tous les chemins est-il à exclure ?
• Écrire une fonction somme_max(pyramide) qui remonte de la base vers le sommet, et donner le résultat sur l'exemple.
• Un algorithme glouton qui choisit à chaque étage le plus grand des deux nombres trouve-t-il l'optimum ici ?