Sometimes when faced with a challenge, it can be a good idea to think: What if I work backwards? Sometimes working from the other direction can be a big advantage working from the other direction can be a big advantage. A different approach to this problem would be to work backwards.
Edit: after some debugging of your code, your approach is actually quite fast and very similar to what I started doing here. We just don't use the same order when iterating over the triangle. But if you want to see what I ended up with, take a look at my question at my question.
Sometimes when faced with a challenge, it can be a good idea to think: What if I work backwards? Sometimes working from the other direction can be a big advantage. A different approach to this problem would be to work backwards.
Edit: after some debugging of your code, your approach is actually quite fast and very similar to what I started doing here. We just don't use the same order when iterating over the triangle. But if you want to see what I ended up with, take a look at my question.
Sometimes when faced with a challenge, it can be a good idea to think: What if I work backwards? Sometimes working from the other direction can be a big advantage. A different approach to this problem would be to work backwards.
Edit: after some debugging of your code, your approach is actually quite fast and very similar to what I started doing here. We just don't use the same order when iterating over the triangle. But if you want to see what I ended up with, take a look at my question.
Edit: after some debugging of your code, your approach is actually quite fast and very similar to what I started doing here. We just don't use the same order when iterating over the triangle. But if you want to see what I ended up with, take a look at my question .
The fact that I thought your code was slower than it actually was might be an indication about the readability of your code. I think that by getting rid of the recursion the way I did the actual algorithm used is more apparent, and thus it is more clear that the time complexity is not \$O(2^n)\$ which it looks like at first glance.
Edit: after some debugging of your code, your approach is actually quite fast and very similar to what I started doing here. We just don't use the same order when iterating over the triangle. But if you want to see what I ended up with, take a look at my question .
The fact that I thought your code was slower than it actually was might be an indication about the readability of your code. I think that by getting rid of the recursion the way I did the actual algorithm used is more apparent, and thus it is more clear that the time complexity is not \$O(2^n)\$ which it looks like at first glance.
###Working backwards
Sometimes when faced with a challenge, it can be a good idea to think: What if I work backwards? Sometimes working from the other direction can be a big advantage . A different approach to this problem would be to work backwards.
[2],
[3,4],
[6,5,7],
[4,1,8,3]
Start at the bottom row. On this row, we can find that the 8 is irrelevant as it is right in the middle of two much smaller numbers that can be reached instead, from the same parents that can reach the 8. The same way, we can see that the 4 is a much worse choice than the 1. So the information we want from that row is [*, 1, *, 3].
Now on to the next row! [6, 5, 7]. We find out that the 6 is totally irrelevant as the 5 can also be reached from the same parent (the 3 above). Additionally, the only child of 5 is 1, but the child of 7 is 3. As 1 + 5 < 3 + 7, 1 + 5 does seem like a better route so far. But to be safe, I would store the sum for each of the current 'nodes'. So for the 5, store 1 + 5 = 6. For the 7, store 3 + 7 = 10.
On to the next row! [3, 4]. Here we can find out that the 3 is much better, as the only way the 4 is relevant is because 3 + 7 = 10. But as 1 + 5 + 3 = 9 is smaller than 3 + 7 + 4 = 14, and the 3 and 4 are neighbors, we can totally forget about the 3 + 7 + 4 = 14 path, as it is now irrelevant thanks to our superior 1 + 5 + 3 = 9 path.
Last row, [2]. Here we don't have any choice, so we just add the 2 to our current 1 + 7 + 3 = 9 path and we end up with 11.
###Working backwards
Sometimes when faced with a challenge, it can be a good idea to think: What if I work backwards? Sometimes working from the other direction can be a big advantage . A different approach to this problem would be to work backwards.
[2],
[3,4],
[6,5,7],
[4,1,8,3]
Start at the bottom row. On this row, we can find that the 8 is irrelevant as it is right in the middle of two much smaller numbers that can be reached instead, from the same parents that can reach the 8. The same way, we can see that the 4 is a much worse choice than the 1. So the information we want from that row is [*, 1, *, 3].
Now on to the next row! [6, 5, 7]. We find out that the 6 is totally irrelevant as the 5 can also be reached from the same parent (the 3 above). Additionally, the only child of 5 is 1, but the child of 7 is 3. As 1 + 5 < 3 + 7, 1 + 5 does seem like a better route so far. But to be safe, I would store the sum for each of the current 'nodes'. So for the 5, store 1 + 5 = 6. For the 7, store 3 + 7 = 10.
On to the next row! [3, 4]. Here we can find out that the 3 is much better, as the only way the 4 is relevant is because 3 + 7 = 10. But as 1 + 5 + 3 = 9 is smaller than 3 + 7 + 4 = 14, and the 3 and 4 are neighbors, we can totally forget about the 3 + 7 + 4 = 14 path, as it is now irrelevant thanks to our superior 1 + 5 + 3 = 9 path.
Last row, [2]. Here we don't have any choice, so we just add the 2 to our current 1 + 7 + 3 = 9 path and we end up with 11.