DP with BackTracking ??

Revision en2, by omggg, 2020-03-27 13:27:19

For questions like: (Rat in a maze) In 2-d matrix, given starting point and destination point.. with some points blocked or something, you have to calculate number of paths to reach destination ( given 4 types of moves)... Can I apply DP with it? Memorizing the state Dp[x][y], and using it if i visit that node again??

When i backtrack, how do i un-visit that node and alter DP table with that?

For Eg: 540C - Ice Cave or 374C - Inna and Dima

Any help will be much appreciated. Thanks a lot :)

Tags #backtracking, backtracking, #recursion, #dynamic programming, dp with recursion, 2-dimensional, rat in a maze, maze

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English omggg 2020-03-27 13:27:19 82
en1 English omggg 2020-03-27 13:25:51 609 Initial revision (published)