2290. Minimum Obstacle Removal to Reach Corner | !DP | Dijkstras | 0-1 BFS | Graphs

[@Unknown373d]

great vid

[@usirikayalaharish787]

class Solution: def minimumObstacles(self, grid: List[List[int]]) -> int: def f(i, j): if i == m - 1 and j == n - 1: return 0 if (i, j) in dp: return dp[(i, j)] mini = float('inf') vis.add((i, j)) for r, c in [[0,-1], [0,1],[1,0],[-1,0]]: nr, nc = r + i, c + j if 0

[@KrishnaSharma-bv5ys]

Still didn’t get, why dp won’t work here😢

[@ARYANMITTAL]

okay, think other way around, tell me what approach you would have taken if you would have used dp?

[@anuragsingh7100]

@@ARYANMITTAL class Solution { int m,n; int solve(int i,int j,vector& grid,vector& ans){ if(i==m-1&&j==n-1) return grid[i][j]; if(ans[i][j]!=INT_MAX) return ans[i][j]; int d[]={-1,0,1,0,-1}; int a=INT_MAX; for(int k=0;k=0&&nr=0&&nc

[@JIGARSINGTHAKOR-yy6qp]

In dp you can have subproblem to solve complete problem But here you cannot divide the problem into subproblem as all the 4 direction are possible.

[@KrishnaSharma-bv5ys]

@ By visiting all directions and take a visited matrix to track visited cells.