不同路径的数目(一)

[编程题]不同路径的数目(一)

热度指数：109204 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一个机器人在m×n大小的地图的左上角（起点）。

机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。

可以有多少种不同的路径从起点走到终点？

备注：m和n小于等于100,并保证计算结果在int范围内

数据范围： $0 < n,m \le 100$ ，保证计算结果在32位整型范围内

要求：空间复杂度 $O(nm)$ ，时间复杂度 $O(nm)$

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(min(n,m))$

示例1

输入

2,1

输出

示例2

输入

2,2

输出

算法知识视频讲解

查看答案及解析

Python

wengJJ

Python

利用路线和的规律构建矩阵

0	1	1	1	1
1	2	3	4	5
1	3	6	10	15
1	4	10	20	35

#
# 
# @param m int整型 
# @param n int整型 
# @return int整型
#
class Solution:
    def uniquePaths(self , m , n ):
        # write code here
#         迭代法
        if m==0&nbs***bsp;n==0:
            return 0
        if m==1&nbs***bsp;n==1:
            return 1
        data = [[1]*m for i in range(n)]
        for i in range(1,n):
            for j in range(1,m):
                data[i][j] = data[i][j-1] + data[i-1][j]
        return data[n-1][m-1]
#         递归法 超时
#         if m==0&nbs***bsp;n==0:
#             return 0
#         if m==1&nbs***bsp;n==1:
#             return 1
#         return self.uniquePaths(m-1,n)+self.uniquePaths(m,n-1)

发表于 2021-04-26 11:16:36 回复(0)

Python

牛客264443287号

这题最基本的思路就是F[i,j]=F[i-1,j]+F[i,j-1]，一开始的思路是先设个初始值F[2,1]和F[1,2]等与1然后递归，但是总是超时，那么就只能考虑用空间换时间，所以我用字典来保存m,n的结果，然后通过循环计算到m,n的结果最后返回，代码很简单随便看看就能懂

# @param m int整型 
# @param n int整型 
# @return int整型
#
class Solution:
    def uniquePaths(self , m , n ):
        li={}
        for a in range(1,m+1):
            li[a,1]=1
        for a in range(1,n+1):
            li[1,a]=1
        for i in range(2,m+1):
            for j in range(2,n+1):
                li[i,j]=li[i-1,j]+li[i,j-1]
        return li[m,n]

发表于 2021-02-17 12:05:09 回复(0)

Python

是你的浩哥啊

#动态规划python解法

class Solution:

def uniquePaths(self , m , n ):
# write code here
dp=[[1]*n for i in range(m)]
for i in range(1,m):
for j in range(1,n):
dp[i][j]=dp[i-1][j]+dp[i][j-1]
return dp[-1][-1]

发表于 2021-01-22 17:43:50 回复(0)

Python

wuyu123

#python递归求解超时

class Solution:
    def uniquePaths(self , m , n ):
        # write code here
        if m==1 and n==1:
            return 0
        elif m==1&nbs***bsp;n==1:
            return 1
        else:
            return self.uniquePaths(m-1, n) + self.uniquePaths(m, n-1)

发表于 2020-11-10 19:51:50 回复(0)