LeetCode中的题-----不同路径

快来打我* 2022-02-14 06:52 182阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly96aGFvamlhLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70][]

答案：

排列组合问题，横向和纵向加起来肯定是m+n-2步，相当于总数抽取其中n-1或m-1步

class Solution(object):
        def uniquePaths(self, m, n):
            """
            :type m: int
            :type n: int
            :rtype: int
            """
            fn_1 = 1
            fmn_2 = 1
            fm_1 = 1
            for i in range(1,n):
                fn_1 *= i
            for j in range(1,m):
                fm_1 *= j
            for k in range(1, m+n-1):
                fmn_2 *= k 
            return fmn_2 / (fm_1 * fn_1)

python中有直接求阶乘的方法

return math.factorial(m+n-2)//(math.factorial(m-1)*math.factorial(n-1))

动态规划的解题：

直接dfs会超时，此题适合用动态规划或者记忆化搜索，dp方程描述：机器人从开始就一直往右走，只有一种走法（路径），机器人从一开始就一直往下走也只有一种走法（路径），机器人既往右走又往下走的走法（路径）数为从左边往右走的走法（路径）加从上边往下走的走法（路径）之和，dp\[i\]\[j\]表示从(0,0)点到(i,j)点的走法（路径）数。记忆化搜索，记录下每次搜素完的结果，以便下一次搜索再利用，避免重复计算多次。总结，dp是自底向上，是一个逆推的过程，由多个小问题组合成一个大问题，最终根据递推公式算出最终解。（dfs）搜索是自顶向下，由大问题分解为多个类似的小问题，依次求解出小问题，最终回溯，从而将大问题求解出来。

class Solution(object):
        def uniquePaths(self, m, n):
            """
            :type m: int
            :type n: int
            :rtype: int
            """
     
            if ( n == 0) or (m == 0):
                return 0
            if m == 1 and n == 1:
                return 1
            map = [[0 for col in range(n)] for line in range(m)]
    
            
            for line in range(m):
                   for col in range(n):
                        if line == 0 and col == 0:
                            map[line][col] = 1
                        elif line == 0 and col != 0:
                            map[line][col] =  map[line][col - 1] 
                        elif col == 0 and line != 0:
                            map[line][col] = map[line-1][col] 
                        else:
                            map[line][col] = map[line][col - 1] + map[line-1][col]
                            
    
            return map[-1][-1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly96aGFvamlhLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70]: /images/20220214/04b6138608ab424e9e0a9ffca67b0951.png