I saw this problem., and tried solving it using DP(since i solved similar problems like this using DP) .
But, I wasn’t able to solve it. Also in the editorial and different successful submissions, I saw people using BFS to solve it. How to know if BFS or other graph algos are better choice.