0062. 不同路径

0062. 不同路径 #

  • 标签:数组、动态规划
  • 难度:中等

题目大意 #

给定一个 m*n 的棋盘, 机器人在左上角的位置,机器人每次只能向右、或者向下移动一步。求到达棋盘右下角共有多少条不同的路径。

解题思路 #

可以用动态规划求解,设 $dp[i][j]$ 是从(0,0)到(i,j)的不同路径数。显然 $dp[i][j] = dp[i-1][j] + dp[i][j-1]$。对于第一行、第一列,因为只能超一个方向走,所以 $dp[i][0] = 1,dp[0][j] = 1$。

代码 #

1
2
3
4
5
6
7
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [1] * n
        for i in range(1, m):
            for j in range(1, n):
                dp[j] += dp[j-1]
        return dp[-1]
本站总访问量  次  |  您是本站第  位访问者