美文网首页
Leetcode 62 不同路径

Leetcode 62 不同路径

作者: SunnyQjm | 来源:发表于2020-06-27 09:14 被阅读0次

不同路径

题目

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为“Finish”)。

问总共有多少条不同的路径?

image.png
  • 示例1:

    输入: m = 3, n = 2
    输出: 3
    解释:
    从左上角开始,总共有 3 条路径可以到达右下角。
    1. 向右 -> 向右 -> 向下
    2. 向右 -> 向下 -> 向右
    3. 向下 -> 向右 -> 向右
    
  • 示例2:

    输入: m = 7, n = 3
    输出: 28
    

提示:

  • 1 <= m, n <= 100
  • 题目数据保证答案小于等于 2 * 10 ^ 9

解答

  • 思路:

    • 采用动态规划;

    • dp[i][j] => 第处于第i + 1行第j + 1列的方格,到目的地可走的路径数量

    • 状态转移方程:

      f(i, j) = \begin{cases}f(i + 1, j) + f(i, j + 1), & i + 1 < m \mbox{ and } j + 1 < n \\ f(i + 1, j), &i + 1 < m \mbox{ and } j + 1 == n \\ f(i, j + 1), &i + 1 == m \mbox{ and } j + 1 < n \\ 0, &i + 1 == m \mbox{ and } j + 1 == n\end{cases}

  • 代码:

    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype int
    
        (knowledge)
    
        思路:
        1. 采用动态规划
        2. dp[i][j] => 第处于第i + 1行第j + 1列的方格,到目的地可走的路径数量
        3. 状态转移方程:
            f(i, j) = f(i + 1, j) + f(i, j + 1)    i+1 < m && j+1 < n
                      f(i + 1, j)                  i+1 < m && j+1 == n
                      f(i, j + 1)                  i+1 == m && j+1 < n
                      0                            i+1 == m && j+1 == n
        """
        dp = [[0 for i in range(n)] for i in range(m)]
        dp[m - 1][n - 1] = 1
    
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if i + 1 < m:
                    dp[i][j] += dp[i + 1][j]
                if j + 1 < n:
                    dp[i][j] += dp[i][j + 1]
        return dp[0][0]
    

测试验证

class Solution:
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype int

        (knowledge)

        思路:
        1. 采用动态规划
        2. dp[i][j] => 第处于第i + 1行第j + 1列的方格,到目的地可走的路径数量
        3. 状态转移方程:
            f(i, j) = f(i + 1, j) + f(i, j + 1)    i+1 < m && j+1 < n
                      f(i + 1, j)                  i+1 < m && j+1 == n
                      f(i, j + 1)                  i+1 == m && j+1 < n
                      0                            i+1 == m && j+1 == n
        """
        dp = [[0 for i in range(n)] for i in range(m)]
        dp[m - 1][n - 1] = 1

        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if i + 1 < m:
                    dp[i][j] += dp[i + 1][j]
                if j + 1 < n:
                    dp[i][j] += dp[i][j + 1]
        return dp[0][0]


if __name__ == '__main__':
    solution = Solution()
    print(solution.uniquePaths(3, 2), "= 3")
    print(solution.uniquePaths(7, 3), "= 28")

相关文章

  • 每日一题20201123(62. 不同路径)

    62. 不同路径[https://leetcode-cn.com/problems/unique-paths/] 思路

  • LeetCode第63题: 不同路径uniquePathsWit

    上一题:LeetCode第62题: 不同路径uniquePaths(C语言) 思路:参考62题的思路,递归肯定要直...

  • [LeetCode]62、不同路径

    题目描述 个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。 机器人每次只能向...

  • Leetcode 62 不同路径

    不同路径 题目 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。 机器人每...

  • 【Leetcode】62. 不同路径

    作者: 码蹄疾毕业于哈尔滨工业大学。 小米广告第三代广告引擎的设计者、开发者;负责小米应用商店、日历、开屏广告业务...

  • Leetcode-62:不同路径

    描述:一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。 机器人每次只能向下...

  • LeetCode 62. 不同路径

    题目 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。 机器人每次只能向下...

  • LeetCode-62-不同路径

    解题思路: dp[i][j]表示走到第i-1行、第j-1列时包含的可能路径; 当前点dp[i][j]的可能来源状态...

  • leetcode 62. 不同路径

    题目描述 一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。机器人每次只能向...

  • leetcode62 不同路径

    题目 分析 简单dp问题。边界条件:第一行和第一列全为1,因为上面的每个位置都只有一种方法可以到达。状态转移方程:...

网友评论

      本文标题:Leetcode 62 不同路径

      本文链接:https://www.haomeiwen.com/subject/gwbufktx.html