LeetCode Unique Paths

BabbleDay posted @ 2015年7月17日 19:38 in 刷题防身 with tags python DP leetcode Unique Paths , 992 阅读

基本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)
Avatar_small
Mike F. Thompson 说:
2019年12月24日 21:28

In order to become a PGA pro, a candidate must have attained the age of 18 years and should have a high school diploma. He should also have proof that he is a citizen of the USA. He has to clear PAT or player ability test in which two rounds of golf are played. Each round has a target score and the candidate has to score below the given score <a href="http://zackcreedgolf.weebly.com/">Click Here For More Information</a>.

Avatar_small
Cheque Number 说:
2022年12月20日 03:40

The bank’s issued cheque is essentially a document that instructs a financial institution to pay a certain amount of money from one account to the individual whose name is printed. The individual who writes the cheque is referred to as a drawer. Cheque Number Account holders need to keep the cash in a transaction banking account to approve it without rejection or failure.

Avatar_small
Important Question P 说:
2023年2月14日 22:24

Important Question Paper 2024 Every one of the students are right now sitting tight for the test Model Paper to be Download, so need to reveal to you that as per the data got from the sources as of late, Important Question Paper 2024 The board will deliver its test Previous Paper, realizing that it will be made accessible to you. Board of Secondary Education is otherwise called The Educational board leads secondary school and transitional board tests each year.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter