leetcode之Unique Paths

这题是应用动态规划的。选择出口作为基准点。

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        a = [1] * m
        b = [a] * n
        for i in range(1, len(b)):
            for j in range(1, len(b[0])):
                b[i][j] = b[i - 1][j] + b[i][j - 1]
        return b[n-1][m-1]
           

根据b[i][j] = b[i - 1][j] + b[i][j - 1]公式一步步向上推算，最终返回最左上角的数字。代码如下：