Problem 67: Maximum Path Sum II
View on Project EulerProject Euler Problem 67 Solution
EulerSolve provides an optimized solution for Project Euler Problem 67, Maximum Path Sum II, with C++, Python, Java, and a step-by-step mathematical explanation.
Problem Summary The input is a triangle of integers with 100 rows. If the entry in row \(i\) and column \(j\) is denoted by \(a_{i,j}\) with \(0 \le j \le i < 100\), a valid path starts at \(a_{0,0}\) and, at each step, moves either to \(a_{i+1,j}\) or to \(a_{i+1,j+1}\). The task is to maximize the sum of all visited entries. Since there are 99 downward choices, a brute-force search would have to inspect \(2^{99}\) different paths, so the problem must be reduced mathematically rather than solved by enumeration. Mathematical Approach The central idea is that once a path reaches a given cell, the best continuation below that cell no longer depends on the earlier part of the path. That makes the triangle a natural dynamic-programming object. The right state: the best suffix sum from a cell Define \(F(i,j)\) to be the maximum total obtainable from cell \((i,j)\) down to the base of the triangle, including \(a_{i,j}\) itself. With this notation, the required answer is simply \(F(0,0)\). On the last row there is no choice left, so the boundary condition is immediate: $$F(n-1,j)=a_{n-1,j}, \qquad 0 \le j < n,$$ where \(n=100\). The recurrence comes from the only two legal moves From \((i,j)\) there are exactly two admissible children: \((i+1,j)\) and \((i+1,j+1)\)....
Detailed mathematical approach
Problem Summary
The input is a triangle of integers with 100 rows. If the entry in row \(i\) and column \(j\) is denoted by \(a_{i,j}\) with \(0 \le j \le i < 100\), a valid path starts at \(a_{0,0}\) and, at each step, moves either to \(a_{i+1,j}\) or to \(a_{i+1,j+1}\). The task is to maximize the sum of all visited entries. Since there are 99 downward choices, a brute-force search would have to inspect \(2^{99}\) different paths, so the problem must be reduced mathematically rather than solved by enumeration.
Mathematical Approach
The central idea is that once a path reaches a given cell, the best continuation below that cell no longer depends on the earlier part of the path. That makes the triangle a natural dynamic-programming object.
The right state: the best suffix sum from a cell
Define \(F(i,j)\) to be the maximum total obtainable from cell \((i,j)\) down to the base of the triangle, including \(a_{i,j}\) itself. With this notation, the required answer is simply \(F(0,0)\).
On the last row there is no choice left, so the boundary condition is immediate:
$$F(n-1,j)=a_{n-1,j}, \qquad 0 \le j < n,$$
where \(n=100\).
The recurrence comes from the only two legal moves
From \((i,j)\) there are exactly two admissible children: \((i+1,j)\) and \((i+1,j+1)\). Any optimal path from \((i,j)\) must pick one of those children first and then continue optimally from the chosen child. Therefore
$$F(i,j)=a_{i,j}+\max\bigl(F(i+1,j),\,F(i+1,j+1)\bigr), \qquad 0 \le i < n-1,\; 0 \le j \le i.$$
This recurrence compresses the entire subtriangle below \((i,j)\) into one number: the best path sum available from that point onward.
Why a bottom-up sweep is correct
If the rows are processed in the order \(n-2,n-3,\dots,0\), then when row \(i\) is updated, both children of every cell in that row already store their correct \(F\)-values. Replacing each entry by its value plus the larger child therefore produces the correct \(F(i,j)\) for every position in row \(i\).
This gives a clean invariant: after finishing row \(i\), every entry in that row equals the best possible total from that cell to the bottom. By induction on the row index, the invariant propagates all the way to row 0, and the single entry at the top becomes the global optimum.
The same invariant also explains why the computation can be done in place. Once row \(i+1\) has been used to update row \(i\), the original values in row \(i+1\) are never needed again, so the triangle itself can serve as the dynamic-programming table.
Worked example
Consider the sample triangle with rows \(3\), \(7,4\), \(2,4,6\), and \(8,5,9,3\). The last row is already final. Moving one row upward gives
$$\bigl(2+\max(8,5),\;4+\max(5,9),\;6+\max(9,3)\bigr)=(10,13,15).$$
The next row becomes
$$\bigl(7+\max(10,13),\;4+\max(13,15)\bigr)=(20,19),$$
and the top entry becomes
$$3+\max(20,19)=23.$$
So the optimal path sum is 23, realized by the path \(3 \to 7 \to 4 \to 9\).
Why brute force loses and the recurrence wins
A path-by-path search grows exponentially because every step branches into two possible continuations. The recurrence avoids that explosion by solving each subtriangle once. For a 100-row triangle there are only \(100 \cdot 101 / 2 = 5050\) cells, so the entire problem collapses to a short pass over those entries instead of an astronomical search through \(2^{99}\) full paths.
How the Code Works
Reading the triangle into a mutable structure
The C++, Python, and Java implementations read the input as text, split it into lines, ignore blank lines, and parse each row into integers. The resulting nested container has row lengths \(1,2,3,\dots,100\), matching the geometry assumed by the recurrence.
Overwriting rows from the base upward
They then iterate from the second-last row toward the top. For each entry, the implementation adds the larger of the two children directly below it. After one complete pass over a row, that row no longer stores raw triangle values; it stores the best suffix sums defined by \(F(i,j)\). When the loop reaches the top, the single remaining value is the maximum path sum for the whole triangle.
Sanity check before the full run
Each implementation includes a built-in checkpoint using the standard four-row sample. That check confirms that the bottom-up update produces 23 before the full 100-row triangle is processed. Aside from lightweight argument handling for the input source, the program is essentially the recurrence written directly into code.
Complexity Analysis
If the triangle has \(n\) rows, then it contains \(N=n(n+1)/2\) entries. The algorithm performs one update for every entry outside the last row, so the running time is \(\Theta(N)=\Theta(n^2)\). For Problem 67, \(N=5050\), which is tiny compared with \(2^{99}\).
The extra memory usage is \(O(1)\) beyond the mutable triangle, because the dynamic-programming values are written back into the same structure. If the input had to remain unchanged, the same recurrence could still be evaluated with an \(O(n)\) buffer containing one row of suffix sums.
Footnotes and References
- Problem page: Project Euler 67
- Dynamic programming: Wikipedia - Dynamic programming
- Recurrence relations: Wikipedia - Recurrence relation
- Principle of optimality: Wikipedia - Principle of optimality
Problem 67 source code
C++
#include <algorithm>
#include <fstream>
#include <iostream>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>
namespace {
struct Options {
std::string file = "resources/documents/0067_triangle.txt";
bool run_checkpoints = true;
};
bool parse_string_after_prefix(const std::string& arg,
const std::string& prefix,
std::string& value) {
if (arg.rfind(prefix, 0U) != 0U) {
return false;
}
const std::string tail = arg.substr(prefix.size());
if (tail.empty()) {
return false;
}
value = tail;
return true;
}
bool parse_arguments(int argc, char** argv, Options& options) {
for (int i = 1; i < argc; ++i) {
const std::string arg(argv[i]);
if (arg == "--skip-checkpoints") {
options.run_checkpoints = false;
continue;
}
if (parse_string_after_prefix(arg, "--file=", options.file)) {
continue;
}
std::cerr << "Unknown argument: " << arg << '\n';
return false;
}
return true;
}
std::vector<std::vector<int>> parse_triangle(const std::string& text) {
std::vector<std::vector<int>> triangle;
std::istringstream input(text);
std::string line;
while (std::getline(input, line)) {
if (line.empty()) {
continue;
}
std::istringstream row_stream(line);
std::vector<int> row;
int value = 0;
while (row_stream >> value) {
row.push_back(value);
}
if (!row.empty()) {
triangle.push_back(row);
}
}
return triangle;
}
int max_path_sum(std::vector<std::vector<int>> triangle) {
if (triangle.empty()) {
return 0;
}
for (int row = static_cast<int>(triangle.size()) - 2; row >= 0; --row) {
for (int col = 0; col <= row; ++col) {
triangle[static_cast<std::size_t>(row)][static_cast<std::size_t>(col)] +=
std::max(triangle[static_cast<std::size_t>(row + 1)][static_cast<std::size_t>(col)],
triangle[static_cast<std::size_t>(row + 1)][static_cast<std::size_t>(col + 1)]);
}
}
return triangle[0][0];
}
int solve(const std::string& file_path) {
std::ifstream input(file_path);
if (!input) {
throw std::runtime_error("Could not open triangle file: " + file_path);
}
std::ostringstream buffer;
buffer << input.rdbuf();
return max_path_sum(parse_triangle(buffer.str()));
}
bool run_checkpoints() {
const std::string sample = "3\n7 4\n2 4 6\n8 5 9 3\n";
if (max_path_sum(parse_triangle(sample)) != 23) {
std::cerr << "Checkpoint failed for sample triangle" << '\n';
return false;
}
return true;
}
} // namespace
int main(int argc, char** argv) {
Options options;
if (!parse_arguments(argc, argv, options)) {
return 1;
}
if (options.run_checkpoints && !run_checkpoints()) {
return 2;
}
try {
std::cout << solve(options.file) << '\n';
} catch (const std::exception& ex) {
std::cerr << ex.what() << '\n';
return 3;
}
return 0;
}
Python
import sys
import os
def parse_triangle(text):
triangle = []
for line in text.strip().split('\n'):
if not line.strip():
continue
row = list(map(int, line.split()))
if row:
triangle.append(row)
return triangle
def max_path_sum(triangle):
if not triangle:
return 0
# Work from bottom to top
for row in range(len(triangle) - 2, -1, -1):
for col in range(len(triangle[row])):
triangle[row][col] += max(triangle[row + 1][col], triangle[row + 1][col + 1])
return triangle[0][0]
def solve(file_path):
try:
with open(file_path, 'r') as f:
content = f.read()
except IOError:
raise RuntimeError(f"Could not open triangle file: {file_path}")
return max_path_sum(parse_triangle(content))
def run_checkpoints():
sample = "3\n7 4\n2 4 6\n8 5 9 3"
if max_path_sum(parse_triangle(sample)) != 23:
print("Checkpoint failed for sample triangle", file=sys.stderr)
return False
return True
def main():
# Parse command line arguments
file_path = "resources/documents/0067_triangle.txt"
run_checkpoints_flag = True
i = 1
while i < len(sys.argv):
arg = sys.argv[i]
if arg == "--skip-checkpoints":
run_checkpoints_flag = False
elif arg.startswith("--file="):
file_path = arg[7:]
else:
print(f"Unknown argument: {arg}", file=sys.stderr)
sys.exit(1)
i += 1
if run_checkpoints_flag and not run_checkpoints():
sys.exit(2)
try:
result = solve(file_path)
print(result)
except Exception as ex:
print(str(ex), file=sys.stderr)
sys.exit(3)
if __name__ == "__main__":
main()
Java
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
class Euler67 {
private static class Options {
String file = "resources/documents/0067_triangle.txt";
boolean runCheckpoints = true;
}
private static boolean parseStringAfterPrefix(String arg, String prefix, StringBuilder value) {
if (!arg.startsWith(prefix)) {
return false;
}
String tail = arg.substring(prefix.length());
if (tail.isEmpty()) {
return false;
}
value.setLength(0);
value.append(tail);
return true;
}
private static boolean parseArguments(String[] args, Options options) {
for (String arg : args) {
if ("--skip-checkpoints".equals(arg)) {
options.runCheckpoints = false;
continue;
}
StringBuilder value = new StringBuilder();
if (parseStringAfterPrefix(arg, "--file=", value)) {
options.file = value.toString();
continue;
}
System.err.println("Unknown argument: " + arg);
return false;
}
return true;
}
private static List<List<Integer>> parseTriangle(String text) {
List<List<Integer>> triangle = new ArrayList<>();
String[] lines = text.split("\n");
for (String line : lines) {
line = line.trim();
if (line.isEmpty()) {
continue;
}
String[] tokens = line.split("\\s+");
List<Integer> row = new ArrayList<>();
for (String token : tokens) {
row.add(Integer.parseInt(token));
}
if (!row.isEmpty()) {
triangle.add(row);
}
}
return triangle;
}
private static int maxPathSum(List<List<Integer>> triangle) {
if (triangle.isEmpty()) {
return 0;
}
for (int row = triangle.size() - 2; row >= 0; row--) {
for (int col = 0; col <= row; col++) {
int currentValue = triangle.get(row).get(col);
int leftChild = triangle.get(row + 1).get(col);
int rightChild = triangle.get(row + 1).get(col + 1);
triangle.get(row).set(col, currentValue + Math.max(leftChild, rightChild));
}
}
return triangle.get(0).get(0);
}
private static int solve(String filePath) throws IOException {
BufferedReader reader = new BufferedReader(new FileReader(filePath));
StringBuilder buffer = new StringBuilder();
String line;
while ((line = reader.readLine()) != null) {
buffer.append(line).append("\n");
}
reader.close();
return maxPathSum(parseTriangle(buffer.toString()));
}
private static boolean runCheckpoints() {
String sample = "3\n7 4\n2 4 6\n8 5 9 3\n";
if (maxPathSum(parseTriangle(sample)) != 23) {
System.err.println("Checkpoint failed for sample triangle");
return false;
}
return true;
}
public static void main(String[] args) {
Options options = new Options();
if (!parseArguments(args, options)) {
System.exit(1);
}
if (options.runCheckpoints && !runCheckpoints()) {
System.exit(2);
}
try {
System.out.println(solve(options.file));
} catch (Exception ex) {
System.err.println(ex.getMessage());
System.exit(3);
}
}
}