leetcode 62:不同路径 + 63:不同路径 II

62. 不同路径

package com.example.lettcode.dailyexercises;

import java.util.Arrays;

/**
 * @Class UniquePaths
 * @Description 62. 不同路径
 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
 * 问总共有多少条不同的路径？
 * <p>
 * 例如，上图是一个7 x 3 的网格。有多少可能的路径？
 * <p>
 * 示例 1:
 * 输入: m = 3, n = 2
 * 输出: 3
 * 解释:
 * 从左上角开始，总共有 3 条路径可以到达右下角。
 * 1. 向右 -> 向右 -> 向下
 * 2. 向右 -> 向下 -> 向右
 * 3. 向下 -> 向右 -> 向右
 * <p>
 * 示例 2:
 * 输入: m = 7, n = 3
 * 输出: 28
 * 提示：
 * 1 <= m, n <= 100
 * 题目数据保证答案小于等于 2 * 10 ^ 9
 * @Author
 * @Date 2020/7/6
 **/
public class UniquePaths {
}

/**
 * 解法1:动态规划,时间复杂度O(n^2),空间复杂度O(n^2)
 */
public static int uniquePaths(int m, int n) {
	if (m == 0 || n == 0) return 0;

	int[][] dp = new int[m][n];
	for (int i = 0; i < m; i++) {
		dp[i][0] = 1;
	}
	for (int j = 0; j < n; j++) {
		dp[0][j] = 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];
}

/**
 * 解法2:动态规划,空间复杂度O(2n),时间复杂度O(n^2),
 */
public static int uniquePaths(int m, int n) {
	if (m == 0 || n == 0) return 0;

	// 由于dp[i][j] = dp[i-1][j] + dp[i][j-1]，因此只需要保留当前行与上一行的数据
	int[] pre = new int[n];
	int[] cur = new int[n];
	Arrays.fill(pre, 1);
	Arrays.fill(cur,1);
	for (int i = 1; i < m;i++){
		for (int j = 1; j < n; j++){
			cur[j] = cur[j-1] + pre[j];
		}
		pre = cur.clone();
	}
	return pre[n-1];
}

/**
 * 解法3:动态规划,空间复杂度O(n),时间复杂度O(n^2),
 */
public static int uniquePaths(int m, int n) {
	if (m == 0 || n == 0) return 0;

	int[] cur = new int[n];
	Arrays.fill(cur,1);
	for (int i = 1; i < m;i++){
		for (int j = 1; j < n; j++){
			// 其等价于cur[j] = cur[j-1] + pre[j];
			cur[j] = cur[j-1] + cur[j];
		}
	}
	return cur[n-1];
}

// 测试用例
public static void main(String[] args) {
	int m = 3;
	int n = 2;
	int ans = uniquePaths(m, n);
	System.out.println("UniquePaths demo01 result:" + ans);

	m = 7;
	n = 3;
	ans = uniquePaths(m, n);
	System.out.println("UniquePaths demo01 result:" + ans);
}

63. 不同路径 II

/**
 * @Class UniquePathsWithObstacles
 * @Description 63. 不同路径 II
 * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
 * 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
 * <p>
 * 网格中的障碍物和空位置分别用 1 和 0 来表示。
 * <p>
 * 说明：m 和 n 的值均不超过 100。
 * <p>
 * 示例 1:
 * 输入:
 * [
 * [0,0,0],
 * [0,1,0],
 * [0,0,0]
 * ]
 * 输出: 2
 * 解释:
 * 3x3 网格的正中间有一个障碍物。
 * 从左上角到右下角一共有 2 条不同的路径：
 * 1. 向右 -> 向右 -> 向下 -> 向下
 * 2. 向下 -> 向下 -> 向右 -> 向右
 * @Author
 * @Date 2020/7/6
 **/
public class UniquePathsWithObstacles {
}

/**
 * 动态规划
 */
public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
	if (obstacleGrid == null || obstacleGrid.length == 0) return 0;

	int row = obstacleGrid.length;
	int col = obstacleGrid[0].length;
	if (obstacleGrid[0][0] == 1) return 0;

	int[][] dp = new int[row][col];
	dp[0][0] = 1 - obstacleGrid[0][0];

	// 边界条件
	for (int i = 1; i < row; i++) {
		dp[i][0] = (dp[i - 1][0] == 1 && obstacleGrid[i][0] == 0) ? 1 : 0;
	}
	for (int j = 1; j < col; j++) {
		dp[0][j] = (dp[0][j - 1] == 1 && obstacleGrid[0][j] == 0) ? 1 : 0;
	}
	for (int i = 1; i < row; i++) {
		for (int j = 1; j < col; j++) {
			if (obstacleGrid[i][j] == 0) {
				dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
			}
		}
	}

	return dp[row - 1][col - 1];
}

public static void main(String[] args) {
	int[][] obstacleGrid = new int[][]{
			{0, 0, 0},
			{0, 1, 0},
			{0, 0, 0}
	};
	int ans = uniquePathsWithObstacles(obstacleGrid);
	System.out.println("UniquePathsWithObstacles demo01 result:" + ans);

	obstacleGrid = new int[][]{
			{0, 0},
			{0, 0},
	};
	ans = uniquePathsWithObstacles(obstacleGrid);
	System.out.println("UniquePathsWithObstacles demo02 result:" + ans);
}