A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
DP:用一个二维数组,map[i][j] 到此点可能的路线数量,map[i][j] = map[i - 1][j] + map[i][ j - 1]。我们可以用一个一维数组来代替。
public class Solution { //Time: O(m*n) Space: O(n) public int uniquePaths(int m, int n) { if (m <= 0 || n <= 0) { return 0; } int[] map = new int[n]; Arrays.fill(map, 1); for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { map[j] = map[j] + map[j - 1]; } } return map[n - 1]; } }
Follow up for "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1 and 0 respectively in the grid.
基本和上一题一样,只需判断是否为障碍物,如是设为0。
public class Solution { //Time: O(m*n) Space: O(n) public int uniquePathsWithObstacles(int[][] obstacleGrid) { if (obstacleGrid == null || obstacleGrid.length == 0 || obstacleGrid[0][0] == 1) { return 0; } int[] map = new int[obstacleGrid[0].length]; map[0] = 1; for (int i = 0; i < obstacleGrid.length; i++) { for (int j = 0; j < obstacleGrid[0].length; j++) { if (obstacleGrid[i][j] == 1) { map[j] = 0; } else if (j > 0) { map[j] += map[j - 1]; } } } return map[obstacleGrid[0].length - 1]; } }
No comments:
Post a Comment