数据结构和算法 -- 动态规划

Posted on   |   In   |     |  

我们再次强调：动态编程的核心在于，如果在一个问题的解决方案中，子问题被重复计算，那么就可以利用记录中间结果，达到用空间换取时间的目的。

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def __init__(self):
        self.cache = dict()
    def f(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n in self.cache:
            return self.cache[n]
        if n == 0 or n == 1:
            return n
        self.cache[n] = self.f(n - 1) + self.f(n - 2)
        return self.cache[n]

例题

70. Climbing Stairs

Problem

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
'''
Dynamic programming.
Induction Rule:
T(n)=T(n-1)+T(n-2)
Base cases:
if n <= 0, then the number of ways should be zero.
if n == 1, then there is only way to climb the stair.
if n == 2, then there are two ways to climb the stairs. One solution is one step by another; the other one is two steps at one time.
The key intuition to solve the problem is that given a number of stairs n, if we know the number ways to get to the points [n-1] and [n-2] respectively, denoted as n1 and n2 , then the total ways to get to the point [n] is n1 + n2. Because from the [n-1] point, we can take one single step to reach [n]. And from the [n-2] point, we could take two steps to get there. There is NO overlapping between these two solution sets, because we differ in the final step.
Now given the above intuition, one can construct an array where each node stores the solution for each number n. Or if we look at it closer, it is clear that this is basically a fibonacci number, with the starting numbers as 1 and 2, instead of 1 and 1.
Recursive method:
- cache, time complexity: O(n), space complexity: O(n)
Follow up:
- space complexity: O(1)
    use two pointers
'''
class Solution(object):
    def __init__(self):
        self.cache = dict()
    # Recursive method
    '''
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 0: return 0
        if n in self.cache:
            return self.cache[n]
        if n==1 or n==2: return n
        self.cache[n] = self.climbStairs(n-1) + self.climbStairs(n-2)
        return self.cache[n]
        '''
    # two pointers
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 0: return 0
        if n == 1 or n == 2: return n
        pre,cur = 1, 2
        for i in range(2,n):
            pre, cur = cur, pre+cur
        return cur

##

Problem

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
'''
Solution:
- subarray: 2 pointers: head,tail
- any repeated work? no   any meaningless work? yes    check the sum-array and we can find that the non-max-sum either subtract one more number or miss one more addition
    that is, for each element in the array, we have two options, either start from this element, or continue to sum up, no other options, and we choose maximum value of these two numbers.
    -->
    cur_sum=max(cur_sum,nums[start]+cur_sum),
    max_sum=(cur_sum,max_sum)
'''
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        cur_sum,max_sum=nums[0],nums[0]
        for start in range(1,len(nums)):
            cur_sum=max(nums[start],nums[start]+cur_sum)
            max_sum=max(cur_sum,max_sum)
        return max_sum
    '''
    # brute-force, time limit exceeded
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums)==0:
            return 0
        global_sum=nums[0]
        for i in range(0,len(nums)-1):
            part_sum=nums[i]
            if part_sum>global_sum:
                global_sum=part_sum
            for j in range(i+1,len(nums)):
                part_sum+=nums[j]
                if part_sum>global_sum:
                    global_sum=part_sum
        part_sum=nums[-1]
        if part_sum>global_sum:
            global_sum=part_sum
        return global_sum
    '''

204. Count Primes

Problem

Description:

Count the number of prime numbers less than a non-negative number, n.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
'''
Primitive idea:
- for each number i from 2-n, exclusive, check if i can be divided by a natural number that is from 2-(i-1), inclusive
- Time complexity: O(n^2)
Followup:
- repeated work? yes, for each number larger than 2, we divided it by 2, for each number larger than 3, we divided it by 3....
- think of it in a reverse way, we can enumerate the multiples of p by counting to n from 2p in increments of p, and mark them in the list as non-prime;
- Time complexity: O(nlog(logn))  
The inner loop does n/i steps, where i is prime => the whole complexity is sum(n/i) = n * sum(1/i). According to prime harmonic series, the sum (1/i) where i is prime is log (log n). In total, O(n*log(log n)).
- Space complexity: O(n)
[Divergence of the sum of the reciprocals of the primes
](https://en.wikipedia.org/wiki/Divergence_of_the_sum_of_the_reciprocals_of_the_primes)
'''
class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n<2: return 0
        isPrime=[True]*n
        isPrime[0:2]=[False]*2
        for i in range(2,int(n**0.5)+1):
            if isPrime[i]:
                isPrime[i*2:n:i]=[False]*((n-1-i*2)/i+1)
        return sum(isPrime)
    '''
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n<2: return 0
        count = 0
        for i in range(2, n):
            if self.isPrime(i):
                count+=1
        return count
    def isPrime(self,n):
        for i in range(2,n):
            if n % i == 0:
                return False
        return True
        '''

96. Unique Binary Search Trees

Problem

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?

For example,
Given n = 3, there are a total of 5 unique BST’s.

Solution

/leetcode95.jpg 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
'''
Taking 1~n as root respectively:
1 as root: # of trees = F(0) * F(n-1)  // F(0) == 1
2 as root: # of trees = F(1) * F(n-2)
3 as root: # of trees = F(2) * F(n-3)
...
n-1 as root: # of trees = F(n-2) * F(1)
n as root:   # of trees = F(n-1) * F(0)
So, the formulation is:
F(n) = F(0) * F(n-1) + F(1) * F(n-2) + F(2) * F(n-3) + ... + F(n-2) * F(1) + F(n-1) * F(0)
# Recursive method
    - count(n)=sum(count(i)*count(n-i-1))
    - use cache
    - time complexity: O(n!)->O(n)
# No need to use recursive. Memorized Search -> Dynamic Programming
    Inductive rule:
        count[n]=sum(count[i]*count[n-i-1])
'''
class Solution(object):
    '''
    # Recursive method
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n<=0: return 0
        return self.count(n,dict())
    def count(self,n,cache):
        if n==0 or n==1: return 1
        if n in cache:
            return cache[n]
        cache[n] = sum([self.count(i,cache)*self.count(n-i-1,cache) for i in range(0,n)])
        return cache[n]
        '''
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 0:
            return 0
        count = [0] * (n + 1)
        count[0] = 1
        for i in range(1, n + 1):
            for j in range(0, i):
                count[i] += count[j] * count[i - j - 1]
        return count[n]

95. Unique Binary Search Trees II

Problem

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1…n.

For example,
Given n = 3, your program should return all 5 unique BST’s shown below.

1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
'''
recursive down
    pass all the nodes that can be selected as a new root down
        leftTree = self.helper(start, rootVal - 1)
        rightTree = self.helper(rootVal + 1, end)
return up
    all possible trees under current root
current level
    build all the possible trees (different combination of left and right treelist )
    - for root i in leftTree and for root j in right tree, build a new root and connect with left and right subtree.
'''
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution(object):
    def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        if n <= 0:
            return []
        return self.helper(1, n)
    def helper(self, start, end):
        # base case
        if start > end:
            return [None]
        res = []
        for rootVal in range(start, end + 1):
            leftTree = self.helper(start, rootVal - 1)
            rightTree = self.helper(rootVal + 1, end)
            for i in leftTree:
                for j in rightTree:
                    root = TreeNode(rootVal)
                    root.left = i
                    root.right = j
                    res.append(root)
        return res

72. Edit Distance

Problem

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
'''
Recursion Rule -> Memorized Search -> DP
Time complexity: O(len1*len2)
Space complexity: O(len1*len2)
'''
class Solution(object):
    '''
    # Memorized Search
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        if not word1 and not word2: return 0
        if len(word1)==0: return len(word2)
        if len(word2)==0: return len(word1)
        return self.match(word1,word2,0,0,[[0 for col in range(len(word2))] for row in range(len(word1))])
    def match(self,word1,word2,i,j,count):
        # base case
        if i==len(word1):
            return len(word2)-j
        if j==len(word2):
            return len(word1)-i
        # base case end
        if count[i][j]!=0:
            return count[i][j]
        if word1[i]==word2[j]:
            res=self.match(word1,word2,i+1,j+1,count)
        else:
            # insert
            insert=self.match(word1,word2,i,j+1,count)
            # delete
            delete=self.match(word1,word2,i+1,j,count)
            # replace
            replace=self.match(word1,word2,i+1,j+1,count)
            res=min(insert,delete,replace)+1
        count[i][j]=res
        return res
        '''
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        if not word1 and not word2:
            return 0
        if len(word1) == 0:
            return len(word2)
        if len(word2) == 0:
            return len(word1)
        count = [[0 for col in range(len(word2) + 1)]
                 for row in range(len(word1) + 1)]
        # initialize
        for i in range(len(word1) + 1):
            count[i][0] = i
        for j in range(len(word2) + 1):
            count[0][j] = j
        for i in range(len(word1)):
            for j in range(len(word2)):
                if word1[i] == word2[j]:
                    count[i + 1][j + 1] = count[i][j]
                else:
                    count[i + 1][j + 1] = min(count[i + 1][j], count[i][j + 1], count[i][j]) + 1
        return count[-1][-1]

303. Range Sum Query - Immutable

Problem

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:

1
2
3
4
5
Given nums = [-2, 0, 3, -5, 2, -1]
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

Note:
You may assume that the array does not change.
There are many calls to sumRange function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class NumArray(object):
    def __init__(self, nums):
        """
        initialize your data structure here.
        :type nums: List[int]
        """
        self.sumArray=[0]
        cur=0
        for i in nums:
            cur+=i
            self.sumArray.append(cur)
    def sumRange(self, i, j):
        """
        sum of elements nums[i..j], inclusive.
        :type i: int
        :type j: int
        :rtype: int
        """
        return self.sumArray[j+1]-self.sumArray[i]
# Your NumArray object will be instantiated and called as such:
# numArray = NumArray(nums)
# numArray.sumRange(0, 1)
# numArray.sumRange(1, 2)

Solution

1
2

304. Range Sum Query 2D - Immutable

Problem

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Range Sum Query 2D
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
Given matrix = [
  [3, 0, 1, 4, 2],
  [5, 6, 3, 2, 1],
  [1, 2, 0, 1, 5],
  [4, 1, 0, 1, 7],
  [1, 0, 3, 0, 5]
]
sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

Note:
You may assume that the matrix does not change.
There are many calls to sumRegion function.
You may assume that row1 ≤ row2 and col1 ≤ col2.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
'''
Solution:
    brute-force: O(n^2) time
    use idea from Range Sum Query - Immutable, for each row, store current sum value of all column value, takes O(n) time to set up, and for sumRange, loop the row and calculate the sum of rows result, also takes O(n) time
    improve: store current sum value of all values on the left and above of current value, takes O(n^2) to setup and O(1) time to get sumRange
'''
'''
O(n^2) setup and O(1) sumRegion
'''
class NumMatrix(object):
    def __init__(self, matrix):
        """
        initialize your data structure here.
        :type matrix: List[List[int]]
        """
        if not matrix: return
        self.m=len(matrix)
        self.n=len(matrix[0])
        self.matrix=[[0]*(self.n+1) for i in range(self.m+1)]
        for row in range(self.m):
            cur=0
            for col in range(self.n):
                cur+=matrix[row][col]
                self.matrix[row+1][col+1]=cur
        for col in range(self.n+1):
            cur=0
            for row in range(self.m+1):
                cur+=self.matrix[row][col]
                self.matrix[row][col]=cur
    def sumRegion(self, row1, col1, row2, col2):
        """
        sum of elements matrix[(row1,col1)..(row2,col2)], inclusive.
        :type row1: int
        :type col1: int
        :type row2: int
        :type col2: int
        :rtype: int
        """
        if not self.matrix: return 0
        return self.matrix[row2+1][col2+1]-self.matrix[row1][col2+1]-(self.matrix[row2+1][col1]-self.matrix[row1][col1])
'''
O(n) setup and O(n) sumRegion
class NumMatrix(object):
    def __init__(self, matrix):
        """
        initialize your data structure here.
        :type matrix: List[List[int]]
        """
        self.matrix=[[0] for i in range(len(matrix))]
        for row in range(len(matrix)):
            cur=0
            for col in matrix[row]:
                cur+=col
                self.matrix[row].append(cur)
    def sumRegion(self, row1, col1, row2, col2):
        """
        sum of elements matrix[(row1,col1)..(row2,col2)], inclusive.
        :type row1: int
        :type col1: int
        :type row2: int
        :type col2: int
        :rtype: int
        """
        cur=0
        for row in xrange(row1,row2+1):
            cur+=self.matrix[row][col2+1]-self.matrix[row][col1]
        return cur
        '''
# Your NumMatrix object will be instantiated and called as such:
# numMatrix = NumMatrix(matrix)
# numMatrix.sumRegion(0, 1, 2, 3)
# numMatrix.sumRegion(1, 2, 3, 4)
徐阿衡 wechat
欢迎关注：徐阿衡的微信公众号
客官，打个赏呗~