【每日算法】2021年03月30日多云不同路径

动态规划

字数统计: 248阅读时长: 1 min

 2021/03/30 

这道题是LeeCode第62题，属于动态规划中的中等难度题目。

题目

解题思路

根据题面，假设机器人在位置(i, j), 不考虑边界条件，则它可以采取的动作有两个：向下(i+1)或者向右(j+1),定义dp[i][j]为机器人从(i,j)点走到点(m-1, n-1)的路径数，则有：dp[i][j] = dp[i+1][j] + dp[i][j+1],

然后我们再来考虑边界条件，当机器人在红框区域(此时 $i =m-1, j \in [0 ~, n-2]$ )、蓝框区域（此时 $ i \in [0, m-2] , j=n-1$ )和点(m-1, n-2)时为边界，当机器人在边界上时，它到终点的距离都为1.

最终答案为dp[0][0]。

实现代码

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1]*n]*m
        for i in range(m-1, -1, -1):
            for j in range(n-1, -1,-1):
                if i == m-1 or j == n-1:
                    continue
                dp[i][j] = dp[i+1][j] + dp[i][j+1]
        return dp[0][0]