p18.cpp

/**
 * Find the maximum total from the top of the triangle to the bottom by
 * moving to adjacent numbers on the row below.
 */

#include <iostream>
#include <algorithm>
#include "euler.h"

BEGIN_PROBLEM(18, solve_problem_18)
  PROBLEM_TITLE("Maximum sum travelling down a triangle of numbers")
  PROBLEM_ANSWER("1074")
  PROBLEM_DIFFICULTY(1)
  PROBLEM_FUN_LEVEL(1)
  PROBLEM_TIME_COMPLEXITY("n^2")
  PROBLEM_SPACE_COMPLEXITY("n^2")
END_PROBLEM()

static const int numbers[15][15] = 
{
  { 75 },
  { 95,64 },
  { 17,47,82 },
  { 18,35,87,10 },
  { 20,4,82,47,65 },
  { 19,1,23,75,3,34 },
  { 88,2,77,73,7,63,67 },
  { 99,65,4,28,6,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,4,68,89,53,67,30,73,16,69,87,40,31 },
  { 4,62,98,27,23,9,70,98,73,93,38,53,60,4,23 },
};

static void solve_problem_18()
{
  int best[15];
  for (int j = 0; j < 15; j++)
  {
    best[j] = numbers[14][j];
  }

  for (int i = 13; i >= 0; i--)
  {
    for (int j = 0; j <= i; j++)
    {
      best[j] = numbers[i][j] + std::max(best[j], best[j+1]);
    }
  }
  std::cout << best[0] << std::endl;
}