Why cannot Rat In a Maze problem be solved by dynamic programming?

user_8108198 0
Viewed 244

The problem I am talking about is the one below :

Consider a rat placed at (0, 0) in a square matrix m[ ][ ] of order n and has to reach the destination at (n-1, n-1). 
The task is to find a sorted array of strings denoting all the possible directions which the rat can take to reach the destination at (n-1, n-1). 
The directions in which the rat can move are ‘U'(up), ‘D'(down), ‘L’ (left), ‘R’ (right).
You cannot visit an already visited cell.

Examples: 

Input : N = 4 
1 0 0 0 
1 1 0 1 
0 1 0 0 
0 1 1 1
Output :
DRDDRR

Input :N = 4 
1 0 0 0 
1 1 0 1 
1 1 0 0 
0 1 1 1
Output :
DDRDRR DRDDRR

Why cannot it be solved by dynamic programming? Can't we store all path strings from a given cell?

Problem Link

backtracking dynamic-programming recursion algorithm
1 Answers

DP only works when you can decompose the problem into smaller problems. For most grid problems that DP works on, there's a limitation that you can only move down and to the right, like LC #62, Unique Paths.

But in this case, you can move in all 4 directions, so the ability to carve out subproblems is no longer available. What would the subproblems be? For the limited-movement version, it's the smaller grid, but when you can move backwards to previous regions, there is no more concept of "smaller grid" that you can define after each movement.

Sure, you mark a cell visited, but that's not really a subproblem in the DP sense that having an answer to the number of paths through the grid without the cell helps you build an answer to the grid with the cell.

In Unique Paths, on the other hand, you can blindly trust the subproblem's answer, add to it to build larger answers, and never need to revisit that area of the grid again.

This is just a graph theory problem which you would solve with an exhaustive recursive traversal. For each stack frame, mark the cell visited, then step in all 4 directions, adding each move to the sequence of moves so far. Whenever you reach the destination, yield the sequence as the next result.

user_62433520
Related