LintCode Q114 Unique Paths in Python

  • Jinhai ZHOU
  • 2 Minutes
  • 2016年12月9日
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
"""
@param n and m: positive integer(1 <= n , m <= 100)
@return an integer
"""
def uniquePaths(self, m, n):
# write your code here
# dynamic programming
# time complexity O(n^2)
dp = {}
for i in xrange(m):
for j in xrange(n):
if i == 0 or j == 0:
dp[(i,j)] = 1
else:
dp[(i,j)] = dp[(i - 1,j)] + dp[(i,j - 1)]
return dp[(m - 1,n - 1)]
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。