[chillee]

I think the problem is easier viewed as just a standard graph traversal (although you can view graph traversals as DP...)

https://ideone.com/rU5COm