Dynamic Programming to the rescue

In my previous blog post I crafted a solution together that created a graph of all possible paths starting from the initial node. Next I filtered out the ones not ending at the goal node. For the paths that were left over I finally calculated the total path cost. As the number of lanes increases you will see that the number of possible paths grows exponentially and my previous code will run into timeouts.

So now i present the same solution but drastically improved using dynamic programming.