4 ms·
That assumes that the path only ever goes right and down. There’s no basis for that assumption in the general case, it’s entirely possible that the shortest pat
by OskarS 5y ago
That assumes that the path only ever goes right and down. There’s no basis for that assumption in the general case, it’s entirely possible that the shortest path has to take a “detour” to avoid some high cost sections. This is a shortest-path problem, not a DP problem.
- n4r9 5y agoAh, I see what you mean. The shortest path could snake around a lot. Not quite as easy as I thought!
- jacobmischka 5y agoYep, I wasted a few hours trying to force the DP solution to work as well before giving up and just using Dijkstra.
- Kwantuum 5y agoAnd in fact, there were detours in pretty much all the solutions I've seen posted online for part 2