Minimum Obstacle Removal to Reach Corner LeetCode solution in Java

1
class Solution {
2
  int[][] grid;
3
  int n, m;
4
  boolean[][] seen;
5
  int[] dx = new int[] {0, 0, 1, -1};
6
  int[] dy = new int[] {1, -1, 0, 0};
7
  int[][] dp;
8
  int finalres;
9

10
  private boolean isValid(int i, int j) {
11
    return Math.min(i, j) >= 0 && i < n && j < m && !seen[i][j];
12
  }
13

14
  private int solve(int i, int j, int cnt) {
15
    if (cnt >= finalres) return finalres;
16
    if (i == n - 1 && j == m - 1) {
17
      return cnt;
18
    }
19
    if (dp[i][j] != Integer.MAX_VALUE) return dp[i][j];
20
    int res = n * m + 1;
21
    seen[i][j] = true;
22
    for (int k = 0; k < 4; k++) {
23
      int newI = i + dx[k], newJ = j + dy[k];
24
      if (isValid(newI, newJ)) {
25
        res = Math.min(res, solve(newI, newJ, cnt + grid[i][j]));
26
      }
27
    }
28
    seen[i][j] = false;
29
    return dp[i][j] = Math.min(dp[i][j], res);
30
  }
31

32
  public int minimumObstacles(int[][] grid) {
33
    this.grid = grid;
34
    this.n = grid.length;
35
    this.m = grid[0].length;
36
    this.seen = new boolean[n][m];
37
    dp = new int[n][m];
38
    finalres = n * m + 1;
39
    for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE);
40
    return solve(0, 0, 0);
41
  }
42
}