Calculate maximum sum from Top to Base of Triangle

[sanalsprasad]

Hi. Here lies my problem - http://projecteuler.net/index.php?section=problems&id=18

I am not sure about what to do.. it says that there is an efficient algorithm ( please notify me if you find out ).Anyways, I want to use brute force here. I can store the numbers in a vector or in an array .. but I am not sure about the algorithm for the computer to check all the paths. If i use for-loops I will have use a lot of them (maybe even hundreds of them)

Thanks in advance
~Sanal

[magnificence7]

Hey,

I did that problem too, but I couldn't figure a way to solve it efficiently, so I brute forced it. Also, I'm not gonna give you the efficient algorithm if I knew:
This is said on the frontpage of Project Euler:

However, there is a fine line between researching ideas and using the answer you found on another website.

Besides, you'll learn more If you think yourself. ;)

I could also provide a semi-efficient way to brute force it, but I won't. ;)

[sanalsprasad]

maginficence7
that really did not help though but with what you said something strikes my mind...
if i represent 0 as going to adjacent left and 1 as moving to adjacent right... i need 15-digit binary number comprising of 0's and 1's regardless of their order so i guess there are 2^15 different possibilities.....
and i'll have to calculate the sum for each combination and maybe brute-force... amybe this would do...

[Albatross]

struct Tree
{
    int data;
    Tree * left;
    Tree * right;
};

-Albatross

[z05DSL3A]

http://en.wikipedia.org/wiki/Longest_path_problem

Edit:

P.S.

i guess there are 2^15 different possibilities.....

As you startat the first node, there are only 2¹⁴ paths that you can take for brute force.

[sanalsprasad]

hey thanks people...that helped a lot. I'll post the solution after completion