That is pretty elegant, kind of wish I’d thought of going backwards. I don’t think the direction is relevant for whether memoization is free or not though. We both just store the accumulated values in a map, and I go forwards. Anyway, the other solutions are faster . And @camilleryr’s is faster than @Damirados’ Reddit “optimal” solution, although I don’t pretend to understand it! Very clever.
Name ips average deviation median 99th %
camilleryr 105.88 K 9.44 μs ±75.62% 9 μs 30 μs
reddit 32.58 K 30.69 μs ±34.14% 28 μs 81 μs
adam 25.09 K 39.86 μs ±24.96% 37 μs 91 μs
hallski 19.81 K 50.49 μs ±27.17% 48 μs 126 μs
bossek 19.45 K 51.42 μs ±27.12% 48 μs 121 μs
kwando 16.00 K 62.51 μs ±30.45% 58 μs 158 μs
Comparison:
camilleryr 105.88 K
reddit 32.58 K - 3.25x slower +21.25 μs
adam 25.09 K - 4.22x slower +30.41 μs
hallski 19.81 K - 5.35x slower +41.05 μs
bossek 19.45 K - 5.44x slower +41.98 μs
kwando 16.00 K - 6.62x slower +53.07 μs
It would be interesting to see how the Agent
answers do, but I’ve looked at this problem for long enough already!