[C/C++] Project Euler #18 Maximum Path Sum I(Dynamic Programming)

This program seemed interesting to me personally.

Problem 18 of Project Euler is about finding the path from the top to the bottom in a triangle of numbers that gives the maximum sum.

Starting from the top number in the given triangle, you move downwards by selecting one of the two adjacent numbers. The goal is to find the path that gives the maximum sum of the numbers you choose along the way.

The most important algorithm is Dynamic Programming.  Dynamic Programming technique is often used to find the optimal value in actual path problems, and this program is no exception.

Although the problem on the site mentions it,

If you don't use dynamic programming, you will end up doing a lot of calculations if there are many paths. This problem has 16,384 possible paths. This is because each number on each layer has two possible paths. Since there are 15 layers in total, the total number of paths is \( 2^{14} = 16,384 \).

However, using dynamic programming, the actual number of path calculations is only 120, which is the total number of numbers. Problem #67 has a 100-layer problem.  In the case of 100 layers, it will be a huge number. Since it is 2 to the 99th power, it is roughly 10 to the 30th power. However, using dynamic programming, the amount of calculation will be limited to about 5,050. (Of course, it will use that much more memory.)

[Execution Result] 

The execution result even shows the path. Actually, just giving the answer would be enough.

I erased the answer for courtesy's sake. Of course, if you search the internet, you'll find places with the answer, right?

When writing the program, I could have written it non-recursively, but I tried writing it recursively.  I think it would be better to write a non-recursive program rather than a recursive one when solving problem #67. (Recursive programs are quite expensive, and can also lead to stack overflow.)

 

path sum

The source code is attached below.

//------------------------------------------------
//    Project Euler #18 - Maximum Path Sum I
//        - by Aubrey Choi
//        - created at 2015-01-14
//------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void printtriangle(int h[], int n);
int getmax(int h[], int d[], int s, int c, int n);

int f[1000];

int main()
{
    char s[] = " 75 95 64 17 47 82 18 35 87 10 20 \
        04 82 47 65 19 01 23 75 03 34 88 02 77 73 07 63 \
        67 99 65 04 28 06 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 04 68 89 53 67 30 73 16 69 87 40 31 04 62 \
        98 27 23 09 70 98 73 93 38 53 60 04 23";

    int h[1000];
    int d[1000];
    int n = 0;

    memset(d, 0, sizeof(d));

    for( char *tok = strtok(s, " ") ; tok ; tok = strtok(0, " ") )
    {
        h[n++] = atoi(tok);
    }

    printf("Ans = %d\n", getmax(h, d, 0, 1, n));

    int c = 0;
    while( c < n )
    {
        h[c] = -h[c];
        c = f[c];
    }

    printtriangle(h, n);
}

int getmax(int h[], int d[], int s, int c, int n)
{
    if( s >= n ) return 0;    
    if( d[s] ) return d[s];
    int a = getmax(h, d, s+c, c+1, n);
    int b = getmax(h, d, s+c+1, c+1, n);
    if( a > b ) { f[s] = s+c; return d[s] = a+h[s]; }
    f[s] = s+c+1; return d[s] = b+h[s];
}

void printtriangle(int h[], int n)
{
    int u = 40;
    for( int i = 0 ;  ; i++ )
    {
        int s = i*(i+1)/2;
        if( n < s+i+1 ) break;
        printf("%*s", u-i*2, "");
        for( int j = 0 ; j < i+1 ; j++ )
        {
            if( h[s+j] < 0 ) printf("\033[1;34m%02d\033[0m ", -h[s+j]);
            else printf("%02d  ", h[s+j]);
        }
        putchar('\n');
    }
}