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
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:
1 2 3 4 5 6 7 8 9 0
That’s 8 possible paths. Do you see a pattern? Let’s describe the path straight down to
7, starting from
D = DOWN R = DOWN AND RIGHT DDD
The (single) path to
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
1 + 3 + 5, the path to the
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.