面试题目搜集之Python 算法题目动态规划问题

来自某大厂

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

逻辑分析

这是一个经典的动态规划问题。我们可以定义一个二维数组dp，其中dp[i][j]表示从左上角到达(i, j)这个格子的不同路径数量。

由于机器人只能向右或向下移动，因此到达(i, j)的路径数量等于到达其上方格子(i-1, j)的路径数量加上到达其左方格子(i, j-1)的路径数量。

（i = 0）和第一列（j = 0）的格子，由于它们只能从一个方向（分别是左方和上方）到达，因此路径数量都是1。

代码实现

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        result = [[1] * m for _ in range(n)]
        for index1 in range(1,n):
            for index2 in range(1,m):
                result[index1][index2] = result[index1 - 1][index2] + result[index1][index2 - 1]
        output = result[-1][-1]
        return output


if __name__ == "__main__":
    re = Solution()
    m=2
    n=3
    result=re.uniquePaths(m,n)
    print(result)