代码随想录 -- 动态规划 -- 不同路径

62. 不同路径 - 力扣（LeetCode）

思路：

• dp[i][j]含义：到达第(i,j)个格子有多少种走法
• 递推公式：dp[i][j]=dp[i-1][j]+dp[i][j-1]
• 初始化：dp[0][j]=1：到达第一行的格子都只有一种走法；dp[i][0]=1：到达第一列的格子也都只有一种走法
• 遍历顺序：从上到下，从左到右

class Solution(object):
    def uniquePaths(self, m, n):
        dp=[[1 for _ in range(n)]for _ 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[m-1][n-1]