CODEWITHSUNDEEP
algorithmdynamic-programmingpath-finding
Ak01
Ak01

Reputation: 390

Why are some grid path problems solvable by DP?

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?)

Upvotes: 0

Views: 821

Answers (2)

Ishraaq Parvez
Ishraaq Parvez

Reputation: 136

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.

Upvotes: 2

Ezio
Ezio

Reputation: 2985

The thing to understand here is that DP is not a problem-solving technique. It is an optimization technique that can be applied to problems that have overlapping subproblems, meaning we get the same problem again and again. Instead of solving the same problem multiple times, we save the results into some data structure(often called DP table) and return the result directly instead of calculating the same problems again.

Coming back to your problem, DP can be applied to both problems. In the first problem where you can move to all 4 directions, there will be 2 variables which will uniquely define your problem, first the cell you are at and second, the direction which you are moving to. You need the direction because the answer could differ based on the direction you are moving. You can use these 2 states to create your DP state.

The second problem is also is same, but since here you can only move to 2 directions, your DP state has become simpler, you only need to consider 2 directions up and right.

Upvotes: -1

Related Questions