[JAVA] simple classic DP & Recursion solution, but O(m*n) space ㅜㅜ


  • 0
    S
    public class Solution {
        public int uniquePaths(int m, int n) {
            int[][] grid = new int[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    grid[i][j] = -1;
                }
            }
    
            return uniquePaths(grid, m-1, n-1, 0, 0);
        }
    
        private int uniquePaths(int[][] grid, int m, int n, int x, int y) {
            if (x > m || y > n) {
                return 0;
            }
    
            if (x == m && y == n) {
                return 1;
            }
    
            int p = grid[x][y];
            if (p != -1) {
                return p;
            }
    
            return grid[x][y] = uniquePaths(grid, m, n, x + 1, y) + uniquePaths(grid, m, n, x, y + 1);
        }
    }

  • 0
    H

    Actually, we can use O(n) space. Since for each position we only need to know its left and top value. We can use one array to represent the row and update it when visit each row.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.