[C/C++] Project Euler #67 - Maximum Path Sum II

Problem Overview

“This is a problem with a difficulty of only about 5%, so it’s not very hard.
However, it’s a problem that can be solved using basic algorithms such as the A algorithm, and it’s also applicable in many game programming scenarios.”*

This suggests that while the problem is simple, it still provides a good opportunity to apply important foundational algorithms. Problems like this are especially valuable in game development, where pathfinding and optimization are frequent tasks.

Path sum

---

Exponential Paths
“There are 2 possible paths from any point, so if the height is 10, there are 2⁹ = 512 different paths.
Many of these paths share subpaths, so to compute the total, we can use a technique called dynamic programming (DP).”
If a triangle or grid has n levels and each node branches into 2 options below it (e.g., left and right child), the total number of distinct paths is exponential, specifically 2^(n-1) for height n.
However, since many paths overlap, recalculating each one would be inefficient. Dynamic Programming is an ideal way to avoid recomputation by caching or reusing results from overlapping subproblems.

---

Dynamic Programming (DP)
“DP requires additional memory, but I reused the existing data storage without allocating extra space.
That’s usually fine. Each point has at most two incoming paths.
Just take the maximum of the two and assign it as the maximum value for that point.”
This describes a bottom-up DP strategy where, instead of using an extra array or matrix, the input data structure is modified in place to store interim results. This is a common space optimization.
• At each cell, we only need to remember the maximum path sum from its child nodes.
• The recursive relation is:
dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]
where triangle[i][j] is the value at row i, column j.

---

Bottom-Up vs Top-Down
“Although we could solve it top-down, I chose to go from bottom to top.
That way, we can directly find the maximum at the root node.
Also, we don’t need to separately compute the last row, as their values are already the maximum.
This approach also reduces computation compared to going top-down.”

• Top-down with recursion + memoization works, but may involve stack overhead and deeper call trees.
• Bottom-up DP is more efficient, especially in space/time complexity, and directly yields the answer at the root.

In triangle problems (like “maximum path sum” in a triangle), this is especially effective.

//------------------------------------------------
//    Project Euler #67 - Maximum Path Sum II
//        - by Aubrey Choi
//        - created at 2015-04-13
//------------------------------------------------
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define    FN    "p067_triangle.txt"

int main()
{
    uint64_t h[16384];
    int n = 0;
    char s[4096];

    FILE *fi = fopen(FN, "r");
    while( fgets(s, 4096, fi) )
    {
        for( char *tok = strtok(s, " \r\n") ; tok ; tok = strtok(0, " \r\n") )
            h[n++] = atoi(tok);
    }
    fclose(fi);

    printf("n = %d\n", n);

    for( int d = sqrt(2*n)-2; d >= 0 ; d-- )
    {
        int s = d*(d+1)/2;
        int t = (d+1)*(d+2)/2;
        for( int i = 0 ; i < t ; i++ )
        {
            int l = t+i, r = t+i+1;
            h[s+i] += (h[l]>h[r])?h[l]:h[r];
        }
    }

    printf("Ans = %ju\n", h[0]);
}