文章目录
题目描述解题方法方法一：动态规划java代码复杂度分析
方法二：排列组合java代码复杂度分析
相似题目
题目描述
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
输入：m = 3, n = 7
输出：28
示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
示例 3：
输入：m = 7, n = 3
输出：28
示例 4：
输入：m = 3, n = 3
输出：6
提示：
1 <= m, n <= 100题目数据保证答案小于等于 2 * 109
解题方法
方法一：动态规划
我们设
f
(
i
,
j
)
f(i, j)
f(i,j)为机器人从左上角走到
(
i
,
j
)
(i, j)
(i,j)的路径数量，若机器人在
(
i
,
j
)
(i,j)
(i,j)处，则机器人上一步的位置在
(
i
−
1
,
j
)
(i-1,j)
(i−1,j)或者
(
i
,
j
−
1
)
(i,j-1)
(i,j−1)处，由此可推出
当
i
>
0
i > 0
i>0 且
j
>
0
j > 0
j>0 时，
f
(
i
,
j
)
=
f
(
i
−
1
,
j
)
+
f
(
i
,
j
−
1
)
f(i,j) = f(i-1,j) + f(i,j-1)
f(i,j)=f(i−1,j)+f(i,j−1)当
i
=
0
i = 0
i=0 或
j
=
0
j = 0
j=0 时，
f
(
i
,
j
)
=
1
f(i, j) = 1
f(i,j)=1
根据以上规律可完成代码实现。
java代码
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
(
M
∗
N
)
O(M * N)
O(M∗N)，需要遍历一次dp数组。 空间复杂度：
O
(
M
∗
N
)
O(M * N)
O(M∗N)，需要提供dp数组的存储空间。
方法二：排列组合
从左上角到右下角，需要 m - 1 次向下移动，n - 1 次向右移动，一共需要进行 m + n - 2 次移动。满足排列组合的规律，则总的路径条数为
C
m
+
n
−
2
m
−
1
=
(
m
+
n
−
2
)
∗
(
m
+
n
−
1
)
∗
.
.
.
∗
(
n
−
1
)
(
m
−
1
)
!
C^{m - 1}_{m + n - 2}=\frac{(m + n - 2) * (m + n - 1) *...*(n - 1)}{(m-1)!}
Cm+n−2m−1=(m−1)!(m+n−2)∗(m+n−1)∗...∗(n−1)
我们只需要编程实现计算排列组合总数。
java代码
public int uniquePaths(int m, int n) {
// 取m和n之中的较小值，减少计算排列组合的次数。
int small = Math.min(m, n) - 1;
// 类型取double防止相乘的最终结果超出类型范围
double a = 1;
double b = 1;
int total = m + n - 2;
for (int i = 0; i < small; i++) {
a = a * (total - i);
b = b * (i + 1);
}
return (int) (a / b);
}
复杂度分析
时间复杂度：
O
(
m
i
n
(
m
,
n
)
)
O(min(m,n))
O(min(m,n))，计算排列组合需要参与遍历的次数。 空间复杂度：
O
(
1
)
O(1)
O(1)，只需要提供常数级别的空间存储。
相似题目
[leetcode] 63. 不同路径 II
个人公众号 个人小游戏
好文链接
您阅读本篇文章共花了： 大家都在找：
leetcode：leetcode官网中文
算法：算法的三种基本结构
动态规划：动态规划01背包问题
发表评论