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

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:

``````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 `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.

Categories c++ Tags