Unique Path I&II Leetcode

Without DP, trace back

public int uniquePaths(int m, int n) {
        return backtrack(0,0,m,n);
    }
   
    private int backtrack(int r, int c, int m, int n) {
        if (r==m-1 || c== n-1) {
            return 1;
        } else if (r >= m || c >= n) {
            return 0;
        }
        return backtrack(r+1, c, m, n) + backtrack(r, c+1, m, n);
    }

With DP.
 public int uniquePaths(int m, int n) {
        int[][] mat = new int[m+1][n+1];
        for (int i=0; i<=m; i++) {
            for (int j=0; j<=n; j++) {
                mat[i][j] = -1;
            }
        }
        return backtrack(0,0,m,n, mat);
    }
   
    private int backtrack(int r, int c, int m, int n, int[][] mat) {
        if (r==m-1 || c== n-1) {
            return 1;
        } else if (r >= m || c >= n) {
            return 0;
        }
        if (mat[r+1][c] == -1) {
            mat[r+1][c] = backtrack(r+1, c, m, n, mat);
        }
        if (mat[r][c+1] == -1) {
            mat[r][c+1] = backtrack(r, c+1, m, n, mat);
        }
        return mat[r+1][c] + mat[r][c+1];
    }

Unique Path II

Bottom-up Dynamic programming

public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        if (m==0) return 0;
        int n = obstacleGrid[0].length;
        int[][] mat = new int[m+1][n+1];
        mat[m-1][n] = 1;
       
        for (int r=m-1; r>=0; r--) {
            for (int c = n-1; c>=0; c--) {
                mat[r][c] = (obstacleGrid[r][c] == 1) ? 0 : mat[r+1][c] + mat[r][c+1];
            }
        }
        return mat[0][0];
    }