62不同路径

题目: 一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为“Start” ）.机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）.问总共有多少条不同的路径？

来源: https://leetcode-cn.com/problems/unique-paths/

法一: 参考别人代码

思路: 关键是要写成状态转移方程.学会自定义多维list(索引不同)的方法.

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 注意这里乘m的时候,生成的每一列是同一个索引,
        dp = [[1] * n] * m
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i][j - 1] + dp[i - 1][j]
        return dp[-1][-1]

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 这种写法不会有上面的问题,要熟练掌握
        dp = [[0]*(n+1) for i in range(m+1)]
        dp[1][0] = 1
        for i in range(1, m+1):
            for j in range(1, n+1):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m][n]

if __name__ == '__main__':
    duixiang = Solution()
    a = duixiang.uniquePaths(3,4)
    print(a)

View Code

ccc

法二: 数学方法,直接用组合方法计算.