1
$\begingroup$

I am studying some algorithms interview questions and I am seeing many path-based questions like "if a robot is at the top left of a grid and can only move down or to the right, how many paths can take it to the bottom left of the grid". Or similarly sometimes they ask if the particular destination can be reached at all with some obstacles.

I've seen it solved with recursive DP solutions where you essentially start at the beginning state and recursively call the same function on all states reachable from the current state and the base case is when you reach the target state. Also sometimes memoization is used to optimize it.

However I think these types of problems can also be seen as graph traversal problems. The beginning state would be a node and each node has children which are the states that can be reached from the current node creating a directed graph. So finding a path to the target state can be done via a graph traversal algorithm.

So I guess my question is which is what are the tradeoffs for each approach? Or are they in some cases equivalent?

$\endgroup$
1
$\begingroup$

Both approaches are valid. Assuming you're using memoization, they're largely equivalent; two different ways of thinking about the same thing.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.