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.