Leetcode 62. Unique Paths & 63. Unique Paths II
Leetcode 62. Unique Paths & 63. Unique Paths II
好久没刷题了，今天来俩道简单题。
Leetcode 62. Unique Paths Leetcode 63. Unique Paths II 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?
原谅我重新贴一遍题目描述，不是为了凑字数，而是为了让搜索引擎能索引到这篇文章，其实也是算一种简单的SEO。
简单描述下题目，有个机器人要从左上角的格子走到右下角的格子，机器人只能向下或者向右走，总共有多少种可能的路径?
第二题和第一题唯一的不同是第二题多了一些限制，有些格子不能走，但其实这并未增加题目的复杂度。俩道题有个共同的解题方式——动态规划。 关键思路是 到每个格子的路径数只和这个格子左边和上边格子的有关，是到左和上边格子的路径数之和。 用代码描述就是 obstacleGrid[i][j] = obstacleGrid[i-1][j] + obstacleGrid[i][j-1]; 恩，第二题的核心代码就这一行，剩下的就是对初始状态、特殊格子和边界的处理，完整代码如下，仅供参考。
public class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
for (int i = 0; i < obstacleGrid.length; i++) {
for (int j = 0; j < obstacleGrid[0].length; j++) {
if (1 == obstacleGrid[i][j]) { //特殊格子处理
obstacleGrid[i][j] = 0;
continue;
}
if (0 == i + j) { //左上角格子，初始状态处理
obstacleGrid[i][j] = 1;
continue;
} else if (0 == i) { //上边界处理
obstacleGrid[i][j] = obstacleGrid[i][j - 1];
} else if (0 == j) { //左边界处理
obstacleGrid[i][j] = obstacleGrid[i - 1][j];
} else {
obstacleGrid[i][j] = obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1];
}
}
}
return obstacleGrid[obstacleGrid.length-1][obstacleGrid[0].length-1];
}
}第62题也可以用同样的方式解决，但是需要自己创建一个mn的数组。此解法的时间复杂度O(mn) 空间复杂度同是O(m*n)。但其实这道题可以用组合数学的方式解决，可以把空间复杂度降到O(1)。 机器人从左上角走到右下角，总共需要走m+n-2步，向下走了m-1步，向右走n-1步。 这不就变成一个(m+n-2)中选(m-1)或(n-1)的组合数问题了吗？ 如此代码就可以变的非常简短了。
public class Solution {
public int uniquePaths(int m, int n) {
int N = n + m - 2;
int k = m - 1;
double res = 1;
for (int i = 1; i <= k; i++)
res = res * (N - k + i) / i;
return (int)res;
}
} 很遗憾的是因为63题中引入了特殊情况，无法再用数学的方式处理了，貌似只能用DP（反正我是没想到方法）。