Projet Euler 18

problème

Lors du déplacement du sommet du triangle suivant vers le bas, la somme maximale des nombres est de 23.

3 7 4 2 4 6 8 5 9 3 Dans cet exemple 3 + 7 + 4 + 9 = 23.

Lorsque vous déplacez le triangle suivant du sommet vers le bas, trouvez la somme maximale. (Omis) Remarque: Il y a au plus 16 384 itinéraires ici, vous pouvez donc essayer tous les modèles. Le problème 67 est le même problème, mais avec 100 lignes, il ne peut pas être résolu par round robin. Une méthode plus intelligente est nécessaire. http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2018

Répondre

C'est ennuyeux, alors je l'ai terminé par la récursivité.

def get_next_max(i,j,L1,L2):
  if L2[i][j] == 0:
    if i == len(L1)-1:
      L2[i][j] = L1[i][j]
    else:
      L2[i][j] = L1[i][j] + max(get_next_max(i+1,j,L1,L2),get_next_max(i+1,j+1,L1,L2))
  return L2[i][j]
    
def main():
  L1 = [
    [75],
    [95, 64],
    [17, 47, 82],
    [18, 35, 87, 10],
    [20, 04, 82, 47, 65],
    [19, 01, 23, 75, 03, 34],
    [88, 02, 77, 73, 07, 63, 67],
    [99, 65, 04, 28, 06, 16, 70, 92],
    [41, 41, 26, 56, 83, 40, 80, 70, 33],
    [41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
    [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
    [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
    [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
    [63, 66, 04, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
    [04, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 04, 23]
  ]
  L2 = [[0 for j in range(len(L1[i]))] for i in range(len(L1))]
  
  ans = get_next_max(0,0,L1,L2)
  #print ans