62. Unique Paths

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] uniquePaths = new int[m][n];
        uniquePaths[0][0] = 1;
        for (int i = 1; i < m; i++) {
            uniquePaths[i][0] = 1;
        }
        for (int j = 1; j < n; j++) {
            uniquePaths[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                uniquePaths[i][j] = uniquePaths[i - 1][j] + uniquePaths[i][j - 1];
            }
        }
        return uniquePaths[m - 1][n - 1];
    }
}

class Solution {
    public int uniquePaths(int m, int n) {
        return uniquePathsHelper(m - 1, n - 1);
    }
    
    private int uniquePathsHelper(int m, int n) {
        if (m < 0 || n < 0) {
            return 0;
        } else if (m == 0 || n == 0) {
            return 1;
        } else {
            return uniquePathsHelper(m - 1, n) + uniquePathsHelper(m, n - 1);
        } 
    }
}

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] visited = new int[m][n];
        return uniquePaths(m - 1, n - 1, visited);
    }
    
    private int uniquePaths(int m, int n, int[][] visited) {
        if (m < 0 || n < 0) {
            return 0;
        } else if (m == 0 || n == 0) {
            return 1;
        } else if (visited[m][n] > 0) {
            return visited[m][n];
        } else {
            visited[m][n] = uniquePaths(m - 1, n, visited) + uniquePaths(m, n - 1, visited);
            return visited[m][n];
        }
    }
}