文章目录

题目描述解题方法方法一:动态规划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

个人公众号 个人小游戏

好文链接

评论可见,请评论后查看内容,谢谢!!!
 您阅读本篇文章共花了: