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)

最基本DP

def maxSubArray(self, nums):
        output = [nums[0]]
        for i in range(1,len(nums)):
            output.append( max(output[i-1]+nums[i],nums[i]) )
        return max(output)

优化：用变量代替数组

def maxSubArray(self, nums):
        t, rtn = nums[0], nums[0]
        for i in range(1, len(nums)):
            t = max(t+nums[i], nums[i])
            rtn = max(rtn, t)
        return rtn