Suppose I am given a nxn grid with a start and end location, and I need to get all paths from start to end. At each cell, I can move in all 4 directions: up, down, right, left. I need to find all paths from start to end. This problem is a classic problem that can be solved by bfs/dfs (Although bfs is more common because it is more optimized since we need to visit each cell only once).
However, if I say that, now, at each cell, we can only move in 2 directions: right and down. This problem is also solvable by bfs/dfs since it is just a subset of the original problem. However, this can also be solved by dynamic programming. At each cell, we just need to add the number of ways to get to the cell above it and to the left of it.
My question is, how come this question is solvable by dp and not the other one? Is it because of the directions? and if so, what combination of directions can be used for it to still be solvable by dp (For ex, if we could go in 3 direction: left, right, down then is it still solvable by dp?)
Because the second problem depends upon optimal subproblems, while the first one doesn't. To calculate the minimum distance from the top cell, all you need to do is observe that you can arrive at the cell from the cell above it, or from the cell to its left. Both these states have been calculated, sowe can say that this problem has the "optimal substructures" property, which is an immediate indicator of a dynamic programming solution.
However, if you use this method to arrive at the solution for the first problem, you might observe that you CANNOT do this, because you can arrive at the cell, from four ways, from above, from below, from right, from below. Two of these subproblems have not been calculated yet, so you can't use DP and have to think of a second method.