euler18

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

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

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, , is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

--------------------

#include <stdio.h>
#include <stdlib.h>

#define ARRAY_SIZE(a)    (sizeof(a)/sizeof(a[0]))
const int num [] = {
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,
};

enum {
    LEFT,
    RIGHT,
    NONE,
};

int getfloor(int n)
{
    int floor=0;

    while(1) {
        if (floor*(floor+1)/2 > n)
            break;
        floor++;
    }

    return floor-1;
}

int getnum(int floor)
{
    return floor*(floor+1)/2;
}

int left(int *a, int i)
{
    int floor;
    int offset;

    floor = getfloor(i);
    offset = i - getnum(floor);
    if (offset == 0)
        return 0;
    else {
        int index = getnum(floor-1) + offset-1;
        return a[index];
    }
}

int right(int *a, int i)
{
    int floor;
    int offset;

    floor = getfloor(i);
    offset = i - getnum(floor);
    if (offset == floor)
        return 0;
    else {
        int index = getnum(floor-1) + offset;
        return a[index];
    }
}

void output(int *a, int len)
{
    int i;

    for (i=0; i < len; i++)
        printf("%d ", a[i]);
    printf("\n");
}

int judge(int *a, int len)
{
    int max=0;
    int floor;
    int i;

    floor = getfloor(len-1);

    for (i=getnum(floor); i<len; i++) {
        if (a[i] > max)
            max = a[i];
    }

    return max;
}

int main(int argc, const char *argv[])
{

    int i;
    int sum[ARRAY_SIZE(num)];
    int dir[ARRAY_SIZE(num)];

    dir[0] = NONE;
    sum[0] = num[0];
    for (i = 1; i <= ARRAY_SIZE(num); i++) {
        if (left(sum, i) > right(sum, i)) {
            dir[i] = RIGHT;
            sum[i] = num[i] + left(sum, i);
        } else {
            dir[i] = LEFT;
            sum[i] = num[i] + right(sum, i);
        }
    }

    /*
     * output(sum, ARRAY_SIZE(sum));
     * output(dir, ARRAY_SIZE(num));
     */

    printf("result: %d\n", judge(sum, ARRAY_SIZE(sum)));

    return 0;
}

典型的动态规划的思想实现... 呵呵！