LintCode 不同的路径114

2020-01-14 21:36发布

114. 不同的路径

有一个机器人的位于一个 m × n 个网格左上角。

机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角。

问有多少条不同的路径?

样例

Example 1:

Input: n = 1, m = 3
Output: 1	
Explanation: Only one path to target position.

Example 2:

Input:  n = 3, m = 3
Output: 6	
Explanation:
	D : Down
	R : Right
	1) DDRR
	2) DRDR
	3) DRRD
	4) RRDD
	5) RDRD
	6) RDDR

注意事项

n和m均不超过100
且答案保证在32位整数可表示范围内。

class Solution:
    """
    @param m: positive integer (1 <= m <= 100)
    @param n: positive integer (1 <= n <= 100)
    @return: An integer
    """
    def uniquePaths(self, m, n):
        # write your code here   
#求阶乘
def JC(num): res
= 1 for i in range(1,num+1): res=res*i return res nums = JC(m-1)*JC(n-1) all = JC(m+n-2) return all//nums

思路:
m*n
1*3 DD 1 2*1//2*1
3*3 DDRR 6 4*3*2*1//2*1//2*1
63*2 DRRRRRRRRRRRRRRRRRR..... 63 63*62*61*...1//62*61*60*...1//1
1.首先可以根据m*n算出有多少种不同的拼接可能,比如3*3,DDRR,DRDR,DRRD,RRDD,RDRD等 >>不管怎么样到达终点时都是向右2 步,向下2步,所以有D,D,R,R共4个元素,
有4*3*2*1种拼接组合
2.最终有m+n-2的阶乘种拼接组合,但是全部的拼接组合中存在重复的元素,所以需要分别除以m-1的阶乘种拼接组合
和除以n-1的阶乘种拼接组合,得到的就是最终的所有可能了

公式表达:
全部出现的可能:m+n-2的阶乘
重复元素拼接组合的可能:m-1的阶乘,n-1的阶乘
最终可能:m+n-2的阶乘//(m-1的阶乘*n-1阶乘)

标签: