剑指 Offer II 098. 路径的数目

剑指 Offer II 098. 路径的数目 #

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

题目大意 #

给定一个 m * n 的棋盘, 机器人在左上角的位置,机器人每次只能向右、或者向下移动一步。

要求:求出到达棋盘右下角共有多少条不同的路径。

解题思路 #

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

代码 #

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