LeetCode 62. Unique Paths 机器人走格子-动态规划记录_leetcode 走格子的题

题目为机器人从左上角走到右下角，不重复的路径有多少条。

使用动态规划求解，分析如下:

设这个格子的大小为m*n，终点位置（右下角finish）的坐标final = (m-1,n-1)。而final的上一步只有两种可能，

即从左边的（m-2,n-1）向右走一步，或者从上边的(m-1,n-2)向下走一步，而且这两种方式不可能重复，只要把到达

(m-2,n-1)和(m-1,n-2)的路径加起来，就是到达(m-1,n-1)的路径，归纳出转移方程：

$f(x,y) = f(x-1,y)+f(x,y-1)$

需要设定两个边界，即m=0或者n=0时，此时的路径只能横着走或者竖着走，只有一条路径。

初始条件为左上角机器人出发的位置，设$f(0,0) = 0$.

代码如下：

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        # 使用动态规划，终点为(m-1,n-1)
        # 到达终点的上一步有两种方式，左边一格(m-2,n-1)，上边一格(m-1,n-2)
        # 转移方程：f(m,n) = f(m-1,n) + f(m,n-1)
        # 边界：（1）m=0,时，只考虑n；（2）n=0时，只考虑m
        # 初始条件 f(0,0)=1
        
        # 开一个数组保存到达某个格子的路径之和
        p_list = [[0]*n for x in range(m)]
        p_list[0][0] = 1
        
        for i in range(m):
            
            for j in range(n):
                
                # 转移方程
                if i == 0:
                    p_list[i][j] = 1
                elif j == 0:
                    p_list[i][j] = 1
                else:
                    p_list[i][j] = p_list[i-1][j] + p_list[i][j-1]
        
        return p_list[m-1][n-1]

算法思想参考九章算法。