题目地址
题目描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
例如，上图是一个7 x 3 的网格。有多少可能的路径？
示例 1:
输入: m = 3, n = 2
输出: 3
解释:
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向右 -> 向下
2. 向右 -> 向下 -> 向右
3. 向下 -> 向右 -> 向右
示例 2:
输入: m = 7, n = 3
输出: 28
提示：
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10 ^ 9
题解
暴力枚举
通过回溯算法枚举所有的状态，到达终点路径加
1
class Solution {
private int pathNum = 0;
public int uniquePaths(int m, int n) {
pathNum = 0;
dfs(m, n, 1, 1);
return pathNum;
}
public void dfs(int m, int n, int i, int j) {
// 超出范围
if (i > m || j > n) return;
// 到达终点
if (i == m && j == n) {
pathNum++;
return;
}
// case 1，向右移动一步
dfs(m, n, i+1, j);
// case 2，向下移动一步
dfs(m, n, i, j+1);
}
}
超出时间限制，说明有优化方案。
组合数
机器人只能【向下】或【向右】移动一步。
对于一个 m * n 的网格，从左上角移动到右下角，向下要走 m - 1 步，向右要走 n - 1 步。一共走了 (m - 1) + (n - 1) = m + n - 2 步。
这个问题可以看成，从
m + n - 2个移动方向里面选出m - 1个向下的方向，剩余的就是向右。
因此是一个组合数计算的问题。
组合数公式是指从
n个不同元素中，任取m(m <= n)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；
从n个不同元素中取出m(m <= n)个元素的所有组合的个数，叫做n个不同元素中取出m个元素的组合数。用符号C(n,m)表示。
公式写法
C(m,n) = A(m,n) / n!
int 类型溢出
代码如下所示：
class Solution {
private int pathNum = 0;
public int uniquePaths(int m, int n) {
// 可以向下走 (m-1) 步
// 可以向右走 (n-1) 步
int cN = (m-1) + (n-1);
int cM = (m-1);
return C(cN, cM);
}
/**
组合数公式：C(n,m)=n!/((n-m)!*m!)（m≤n）
*/
public int C(int n, int m) {
return factorial(n) / (factorial(n - m) * factorial(m));
}
public int factorial(int n) {
if (n == 0 || n == 1) {
return 1;
}
return factorial(n-1) * n;
}
}
int 类型溢出了
long 类型溢出
/**
组合数公式：C(n,m)=n!/((n-m)!*m!)（m≤n）
*/
public int C(int n, int m) {
long result = factorial(n) / (factorial(n - m) * factorial(m));
return (int)result;
}
public long factorial(int n) {
if (n == 0 || n == 1) {
return 1;
}
return factorial(n-1) * n;
}
long 类型也溢出了
BigInteger 存储数值
// 注意需要导出 BigInteger 类
import java.math.*;
class Solution {
private int pathNum = 0;
public int uniquePaths(int m, int n) {
// 可以向下走 (m-1) 步
// 可以向右走 (n-1) 步
int cN = (m-1) + (n-1);
int cM = (m-1);
return C(cN, cM);
}
/**
组合数公式：C(n,m)=n!/((n-m)!*m!)（m≤n）
*/
public int C(int n, int m) {
BigInteger result = factorial(n).divide(factorial(n - m).multiply(factorial(m)));
return result.intValue();
}
public BigInteger factorial(int n) {
if (n == 0 || n == 1) {
return BigInteger.ONE;
}
return factorial(n-1).multiply(BigInteger.valueOf(n));
}
}
动态计算组合数 C(m, n) 的值
/**
组合数公式：C(n,m)=n!/((n-m)!*m!)（m≤n）
*/
public int C(int n, int m) {
int begin = (n-m+1);
long result = 1;
for (int i = 1; i <= m; ++ i) {
result *= begin;
result /= i;
begin++;
}
return (int)result;
}
动态规划
定义
dp[i][j]为当前位置走到右下角的路径数。
因此状态转移方程可以写作：dp[i][j] = dp[i + 1][j] + dp[i][j + 1]。
-
dp[i + 1][j]表示向下移动一步。 -
dp[i][j + 1]表示向右移动一步。
对于一个 m * n 的网格，base case 为：
- 最右边一列只有一条路径，即
dp[i][n - 1] = 1，0 <= i < m。 - 最下面一行只有一条路径，即
dp[m - 1][j] = 1，0 <= j < n。
class Solution {
private int pathNum = 0;
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
// 最右边的一列初始化为 1
for (int i = 0; i < m; ++ i) {
dp[i][n - 1] = 1;
}
// 最下面的一行初始化为 1
for (int j = 0; j < n; ++ j) {
dp[m - 1][j] = 1;
}
// 从未赋值的右下角位置开始遍历
for (int i = m - 2; i >= 0; i --) {
for (int j = n - 2; j >= 0; j --) {
dp[i][j] = dp[i+1][j] + dp[i][j+1];
}
}
return dp[0][0];
}
}
