Euler #18

https://projecteuler.net/problem=18

Este problema se me resistió un poco al principio por tratar de hacerlo a lo bruto y sin pensar mucho (es decir, calculando todas las posibles rutas).

En StackOverflow encontré una pequeña pista: ir reduciendo cada fila, desde abajo hasta arriba, calculando la máxima suma en cada interacción. Una vez tomada esta aproximación, el código es trivial:

Python:

   1 #!/usr/bin/env python2
   2 data = [
   3 ['75'],
   4 ['95', '64'],
   5 ['17', '47', '82'],
   6 ['18', '35', '87', '10'],
   7 ['20', '04', '82', '47', '65'],
   8 ['19', '01', '23', '75', '03', '34'],
   9 ['88', '02', '77', '73', '07', '63', '67'],
  10 ['99', '65', '04', '28', '06', '16', '70', '92'],
  11 ['41', '41', '26', '56', '83', '40', '80', '70', '33'],
  12 ['41', '48', '72', '33', '47', '32', '37', '16', '94', '29'],
  13 ['53', '71', '44', '65', '25', '43', '91', '52', '97', '51', '14'],
  14 ['70', '11', '33', '28', '77', '73', '17', '78', '39', '68', '17', '57'],
  15 ['91', '71', '52', '38', '17', '14', '91', '43', '58', '50', '27', '29', '48'],
  16 ['63', '66', '04', '68', '89', '53', '67', '30', '73', '16', '69', '87', '40', '31'],
  17 ['04', '62', '98', '27', '23', '09', '70', '98', '73', '93', '38', '53', '60', '04', '23']]
  18 
  19 for row in range(len(data) - 2, -1, -1):
  20     for col in range(row+1):
  21         data[row][col] = max((int(data[row][col]) + int(data[row + 1][col + 0]), int(data[row][col]) + int(data[row + 1][col + 1])))
  22 
  23 print data[0][0]
  24