不同路径
一个机器人位于一个 *m x n *网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
方法一：动态规划
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int i = 0; i < n; i++) {
dp[0][i] = 1;
}
for (int i =1; i < m; i++) {
for (int j =1; j < n; j++) {
dp[i][j] = dp[i -1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
空间优化：
由于当前位置只取决于上一行和当前位置的前一列，所以只需要用一个一维数组保存上一行的计算结果，在遍历每一行的时候得到前一个位置的值
O(2n)：
public int uniquePaths(int m, int n) {
int[] pre = new int[n];
int[] cur = new int[n];
Arrays.fill(pre, 1);
for (int i =1; i < m; i++) {
cur[0] = 1;
for (int j =1; j < n; j++) {
cur[j] = cur[j - 1] + pre[j];
}
pre = cur;
}
return pre[n - 1];
}
O(n)：
public int uniquePaths(int m, int n) {
int[] dp = new int[n];
Arrays.fill(dp, 1);
int pre = 1;
for (int i = 1; i < m; i++) {
pre = 1;
for (int j = 1; j < n; j++) {
dp[j] = pre + dp[j];
pre = dp[j];
}
}
return dp[n - 1];
}
方法二：排列组合（未通过）
m=3, n=2，只要向下 1 步，向右 2 步就一定能到达终点。
所以有 C_{m+n-2}^{m-1}
public int uniquePaths(int m, int n) {
return (int) (factorial(m + n -2) / factorial(n - 1) / factorial(m - 1));
}
public long factorial(int n) {
long sum = 1;
for (int i = 1; i <= n; i++) {
sum *= i;
}
return sum;
}
由于乘积导致溢出，所以未通过
不同路径 II
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示。
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length, n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (obstacleGrid[i][j] != 1) {
if (i == 0 && j== 0) {
dp[i][j] = 1;
} else {
dp[i][j] = (i == 0 ? 0 : dp[i - 1][j]) + (j == 0 ? 0 : dp[i][j - 1]);
}
}
}
}
return dp[m - 1][n - 1];
}
最小路径和
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小
方法一：dfs（超时）
int inf = Integer.MAX_VALUE;
public int minPathSum(int[][] grid) {
return dfs(grid, 0, 0);
}
private int dfs(int[][] grid, int i, int j) {
if (i >= grid.length || j >= grid[0].length) {
return inf;
}
int min = Math.min(dfs(grid, i + 1, j), dfs(grid, i, j + 1));
if (min == inf) {
return grid[i][j];
}
return min + grid[i][j];
}
记忆优化：
int inf = Integer.MAX_VALUE;
int[][] dp;
public int minPathSum(int[][] grid) {
dp = new int[m][n];
return dfs(grid, 0, 0);
}
private int dfs(int[][] grid, int i, int j) {
if (i >= grid.length || j >= grid[0].length) {
return inf;
}
if (dp[i][j] != 0) {
return dp[i][j];
}
int min = Math.min(dfs(grid, i + 1, j), dfs(grid, i, j + 1));
min = (min == inf ? 0 : min) + grid[i][j];
dp[i][j] = min;
return min;
}
方法二：动态规划
public int minPathSum(int[][] grid) {
if (grid == null || grid[0].length == 0) {
return 0;
}
int row = grid.length;
int col = grid[0].length;
int[][] dp = new int[row][col];
dp[0][0] = grid[0][0];
for (int i = 1; i < col; i++) {
dp[0][i] = dp[0][i - 1] + grid[0][i];
}
for (int i = 1; i < row; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[row - 1][col - 1];
}
空间优化：
public int minPathSum(int[][] grid) {
if (grid == null || grid[0].length == 0) {
return 0;
}
int row = grid.length;
int col = grid[0].length;
int[] dp = new int[col];
dp[0] = grid[0][0];
for (int i = 1; i < col; i++) {
dp[i] = dp[i - 1] + grid[0][i];
}
for (int i = 1; i < row; i++) {
dp[0] = dp[0] + grid[i][0];
int pre = dp[0];
for (int j = 1; j < col; j++) {
dp[j] = Math.min(dp[j], pre) + grid[i][j];
pre = dp[j];
}
}
return dp[col - 1];
}
