62. 不同路径

问题62 不同路径 ★★☆☆☆

https://leetcode.cn/problems/unique-paths/

如果能想到以动态规划为思路来解决这个题目，那么这个题目并不难。状态转移方程也很符合直觉，定义dp[i][j]表示从[0, 0]到[i, j]的路径数，dp[i][j]的计算只依赖于dp[i-1][j]和dp[i][j-1]。

值得注意的是，这个题目容易给人一种适合于使用回溯法的错觉，使用回溯法也能计算出正确结果，但是代码实现起来复杂，时间效率也很差。

	public int uniquePaths(int m, int n) {
		int[][] dp = new int[m][n]; // dp[i][j] represents the unique paths from [0,0] to [i,j]
		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, j = 1; i < m && j < n; i++, j++) {
			for (int k = j; k < n; k++) {
				dp[i][k] = dp[i-1][k] + dp[i][k-1];
			}
			for (int k = i; k < m; k++) {
				dp[k][j] = dp[k-1][j] + dp[k][j-1];
			}
		}

		return dp[m-1][n-1];
	}

在 LeetCode 查看