Questions with DP solutions are usually not particularly great for interviews. They usually don't have any solutions in-between brute force and DP. If somebody doesn't come up with a DP solution you, as an interviewer, just learned that they don't know DP, but it doesn't give you too much useful signal on the candidate's skills. DP is just kind of a trick that you can learn to solve this specific type of problems, but knowing the trick is not something that FAANG companies want to test for.
Just wanted to drop by saying that trailrouter looks great. One small suggestion. I'd add an option to avoid cemeteries as (at least in some cultures) running through one could be considered ill-mannered.