BabbleDay's Blog

基本DP O(mn)

def uniquePaths(self, m, n):
        record = []
        record.append([1]*n)
        for i in range(1,m):
            temp = [1]
            for j in range(1,n):
                temp.append(record[-1][j]+temp[-1])
            record.append(temp)
        return record[m-1][n-1]

优化：O(m+n) 二项式系数

递归超时，因为中间部分的格子到目标的路径每次都重新算了一遍，树状重复＝ ＝

def uniquePaths(self, m, n):

        def isValid(x,y):
            return (x<m and x>=0 and y<n and y>=0)
        
        def goNext(x,y):
            if x==m-1 and y==n-1:
                return 1
            if isValid(x,y):
                return goNext(x+1,y) + goNext(x,y+1)
            else:
                return 0
        
        return goNext(0,0)