[Solved] Why I am getting Time Limit Exceeded? [closed]

Question

Why I am getting Time Limit Exceeded?

Consider this triangle (ignore the numbers):

1
2 3

There are 2 possible paths to take here. Let’s add a row:

1
2 3
4 5 6

The 4 can only be reached via a path that ends directly above, the 5 has two paths which can reach it, the 6 can only be reached from the path previously ending left above of it. We now have 4 possible paths. Another row:

That’s 8 possible paths. Do you see a pattern? Let’s describe the path straight down to 7, starting from 1:

D = DOWN
R = DOWN AND RIGHT

DDD

The (single) path to 0:

RRR

Since in each step you go down one row, you can only chose between the two possibilities number of rows - 1 times, thus giving you:

2^(number of rows - 1) possible paths

With 100 rows, that’s alot. Your code tries to compute each of these paths separately. Assuming computing 1 path takes 1 nanosecond (which would be blazing fast) computing them all would take more than 2 * 10^16 years. Well, …

Time Limit Exceeded

So you now know that you cannot just compute every possible path and take the maximum. The main issue is the following:

1
2 3
4 5 6

One path to the 5 is 1 + 3 + 5, the path to the 6 is 1 + 3 + 6. Your code computes each path separately, thus 1 + 3 will be computed twice. If you save that result, you’ll get rid of most of the unnecessary computations.

How could you store such results? Well, 1 + 3 is the computation of the path arriving at 3, so store it there. What if a number (say 5) can be reached by multiple paths?

5 could be reached via 1 + 2 + 5 or 1 + 3 + 5.

Any path going through the 5 will give a higher result if it wen’t through the 3 first, so only remember this path (and ignore the path through the 2, it’s useless now).

So, as an algorithm:

For each row, starting at row 1 (not the first, but the second): For each entry: Calculate the maximum of the entries left above (if available) and directly above (if available) and store the result + the entry’s value as new value for the entry. Then, find the maximum of the last row.

Accepted Answer