https://leetcode.com/problems/unique-paths/

1. recursion:

  1. class Solution(object):
  2.     def uniquePaths(self, m, n):
  3.         """
  4.         :type m: int
  5.         :type n: int
  6.         :rtype: int
  7.         """
  8.         if m==1 or n==1:
  9.             return 1
  11.         return self.uniquePaths(m - 1, n) + self.uniquePaths(m, n - 1)

2. dynamic programming:

  1. class Solution(object):
  2.     def uniquePaths(self, m, n):
  3.         """
  4.         :type m: int
  5.         :type n: int
  6.         :rtype: int
  7.         """
  9.         # set up a m*n matrix, all values are 1
  10.         d = [([1] * n) for _ in range(m)]
  12.         # The number in the matrix represents 
  13.         # the number of paths that could reach the current one for top-left
  14.         # 
  15.         # Also, the one instead of in the 1st row or 1st column are sum of its left one and its upper one
  16.         # 
  17.         # for example, m = 3, n = 4
  18.         # d = 1 1 1 1
  19.         #     1 1 1 1
  20.         #     1 1 1 1
  21.         # -->
  22.         # d = 1 1 1 1
  23.         #     1 2 3 4
  24.         #     1 3 6 10
  25.         for col in range(1, m):
  26.             for row in range(1, n):
  27.                 d[col][row] = d[col - 1][row] + d[col][row - 1]
  30.         return d[m - 1][n - 1]