Problem 18: Maximum Path Sum I

Problem:

Please find the problem here.

Solution:

Instead of solving it by brute force, I think it is easier to solve it with dynamic programming. First, let generalize the problem by asking the question - what is the maximum route from an arbitrary node to bottom? The base case is really simple. If you are trying to go from the bottom row to the bottom row, there is only one route with one node, and therefore the maximum total is the node value itself. Now, if we want to reach the node 2 (1st in the 3rd row) in the first triangle, we will pick the left route because 2 + 8 has a bigger sum than 2 + 5. The rule generally applies. If we want to go to 7 (the 1st in the 2nd row), we pick from its children the one with maximum total.

That translate to a dynamic programming algorithm as follow:

maximum_total_cost(last_row) = last_row value
maximum_total_cost(any node n ) = n + max(maximum_total_cost(left_child) + maximum_total_cost(right_child)).

Without further ado, here is the code for the problem:

namespace Euler
{
    using System;
    using System.Linq;
    using System.Numerics;

    internal static partial class Program
    {
        public static void Problem018()
        {
            string input = ReadResourceAsString("Euler.Problem018.txt");
            int[] inputParsed = input.Replace('\r', ' ').Replace('\n', ' ').Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries).Select(x => Int32.Parse(x)).ToArray();
            int numRows = 15;

            // answer(row, column) = data[row, column] + max(answer(row + 1, column), answer(row + 1, column + 1));

            int[,] answer = new int[numRows, numRows];
            for (int i = 1; i <= numRows; i++)
            {
                answer[i - 1, numRows - 1] = inputParsed[i + numRows * (numRows - 1) / 2 - 1];
            }
            for (int currentRow = numRows - 1; currentRow > 0; currentRow--)
            {
                for (int currentColumn = 1; currentColumn <= currentRow; currentColumn++)
                {
                    int currentValue = inputParsed[currentColumn + currentRow * (currentRow - 1) / 2 - 1];
                    answer[currentColumn - 1, currentRow - 1] = currentValue + Math.Max(answer[currentColumn - 1, currentRow + 1 - 1], answer[currentColumn + 1 - 1, currentRow + 1 - 1]);
                }
            }
            Console.WriteLine(answer[0, 0]);
        }
    }
}

Answer: 1074