侯瑞哲的博客

Ruizhe's Blog

0%

发表于 Valine：

问题描述

https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix

给定一个整数矩阵，找出最长递增路径的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

示例 1:

输入: nums = [ [9,9,4], [6,6,8], [2,1,1]] 输出: 4 解释: 最长递增路径为 [1, 2, 6, 9]。 示例 2:

输入: nums = [ [3,4,5], [3,2,6], [2,2,1]] 输出: 4 解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

思路

我们可以对每一个点求出最长递增路径的长度，这样当相邻的点比该点小的时候，我们将该点的最长递增路径的长度加1，就是这个相邻点的最长递增路径的可能值。

这里面一定不会有重复访问的现象，因为是最长递增路径，不存在相同的值，我们可以放心的使用其他点已经求出的最长递增路径。

那么这个函数的参数也就出来了，dfs(i, j)。i，j表示是哪个点，函数求出的结果是这点为起始的最长递增路径长度。这个函数怎么求呢？首先自身就是一条路径，也就是最少是1。然后我们往四个方向扩散，这里判断越界，并且要确定这四个方向的值比当前大，否则不能扩散，假设我们已经求出了其他几个方向（小于等于四）的最长递增路径，这些方向上的点的值都是比当前大的，那么这个点的最长递增路径长度就是，这几个方向的最长递增路径的最大值加1，最终要和1比较一下更大，因为可能所有方向的值都小于等于当前。

最终我们可以加上记忆化，因为我们一旦算出来i，j的最长递增路径的长度之后，我们就可以重复的使用它，不会改变了。这可以节省时间。

示例代码

示例代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        h, w = len(matrix), len(matrix[0])
        memo = {}

        def dfs(i, j):
            if (i, j) in memo:
                return memo[i, j]
            memo[i, j] = 1
            cur = matrix[i][j]
            for di, dj in ((0, 1), (1, 0), (0, -1), (-1, 0)):
                _i, _j = i + di, j + dj
                if -1 < _i < h and -1 < _j < w \
                        and matrix[_i][_j] > cur:
                    memo[i, j] = max(memo[i, j], 1 + dfs(_i, _j))
            return memo[i, j]

        return max(dfs(i, j) for i in range(h) for j in range(w))

优化空间使用矩阵来记忆化搜索：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        h, w = len(matrix), len(matrix[0])
        memo = [[0] * w for _ in range(h)]

        def dfs(i, j):
            if memo[i][j]:
                return memo[i][j]
            memo[i][j] = 1
            cur = matrix[i][j]
            for dx, dy in ((0, 1), (1, 0), (0, -1), (-1, 0)):
                _i, _j = i + dx, j + dy
                if -1 < _i < h and -1 < _j < w \
                        and matrix[_i][_j] > cur:
                    memo[i][j] = max(memo[i][j], 1 + dfs(_i, _j))
            return memo[i][j]

        return max(dfs(i, j) for i, j in itertools.product(range(h), range(w)))

发表于 更新于 Valine：

参考

https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/

实际问题（简单记，想快速知道数组的前缀和，同时数组的修改频繁，用树状数组，使得这两种操作都变成O(logn)，两边查询的树状数组可以相当于线段树的功能）

We have an array arr[0 . . . n-1]. We would like to 1 Compute the sum of the first i elements. 2 Modify the value of a specified element of the array arr[i] = x where 0 <= i <= n-1.

A simple solution is to run a loop from 0 to i-1 and calculate the sum of the elements. To update a value, simply do arr[i] = x. The first operation takes O(n) time and the second operation takes O(1) time.

Another simple solution is to create an extra array and store the sum of the first i-th elements at the i-th index in this new array. The sum of a given range can now be calculated in O(1) time, but the update operation takes O(n) time now. This works well if there are a large number of query operations but a very few number of update operations.

Could we perform both the query and update operations in O(log n) time? One efficient solution is to use Segment Tree that performs both operations in O(Logn) time.

An alternative solution is Binary Indexed Tree, which also achieves O(Logn) time complexity for both operations. Compared with Segment Tree, Binary Indexed Tree requires less space and is easier to implement..

给定一个数组[0, .., n-1]，我们想：

  1. 计算出前i个元素的和
  2. 将任何一个元素改为x，arr[i] = x where 0<=i<=n-1

和线段树的实际问题的区别在于，线段树是从l到r任何一段，树状数组只是前i个。

同样第一个简单的解法就是循环求和O(n)，改变为O(1)。

或者创建一个新数组的每个元素存的前i个数的和，这样求和就是O(1)，但是改变后数组就要调整O(n)的时间复杂度。

Representation Binary Indexed Tree is represented as an array. Let the array be BITree[]. Each node of the Binary Indexed Tree stores the sum of some elements of the input array. The size of the Binary Indexed Tree is equal to the size of the input array, denoted as n. In the code below, we use a size of n+1 for ease of implementation.

Construction We initialize all the values in BITree[] as 0. Then we call update() for all the indexes, the update() operation is discussed below.

Operations

1
2
3
4
5
6
7
8
getSum(x): Returns the sum of the sub-array arr[0,...,x]
// Returns the sum of the sub-array arr[0,...,x] using BITree[0..n], which is constructed from arr[0..n-1]
1) Initialize the output sum as 0, the current index as x+1.
2) Do following while the current index is greater than 0.
...a) Add BITree[index] to sum
...b) Go to the parent of BITree[index].  The parent can be obtained by removing
     the last set bit from the current index, i.e., index = index - (index & (-index))【index&(index-1) 也可以】
3) Return sum.

The diagram above provides an example of how getSum() is working. Here are some important observations.

BITree[0] is a dummy node.

BITree[y] is the parent of BITree[x], if and only if y can be obtained by removing the last set bit from the binary representation of x, that is y = x – (x & (-x)).【index&(index-1) 也可以】

The child node BITree[x] of the node BITree[y] stores the sum of the elements between y(inclusive) and x(exclusive): arr[y,…,x).

1
2
3
4
5
6
7
update(x, val): Updates the Binary Indexed Tree (BIT) by performing arr[index] += val
// Note that the update(x, val) operation will not change arr[].  It only makes changes to BITree[]
1) Initialize the current index as x+1.
2) Do the following while the current index is smaller than or equal to n.
...a) Add the val to BITree[index]
...b) Go to parent of BITree[index].  The parent can be obtained by incrementing
     the last set bit of the current index, i.e., index = index + (index & (-index))

The update function needs to make sure that all the BITree nodes which contain arr[i] within their ranges being updated. We loop over such nodes in the BITree by repeatedly adding the decimal number corresponding to the last set bit of the current index.

How does Binary Indexed Tree work? The idea is based on the fact that all positive integers can be represented as the sum of powers of 2. For example 19 can be represented as 16 + 2 + 1. Every node of the BITree stores the sum of n elements where n is a power of 2. For example, in the first diagram above (the diagram for getSum()), the sum of the first 12 elements can be obtained by the sum of the last 4 elements (from 9 to 12) plus the sum of 8 elements (from 1 to 8). The number of set bits in the binary representation of a number n is O(Logn). Therefore, we traverse at-most O(Logn) nodes in both getSum() and update() operations. The time complexity of the construction is O(nLogn) as it calls update() for all n elements.

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
# 树状数组binary-indexed-tree.py


class BITree:
    def __init__(self, nums):
        self.n = len(nums)
        self.tree = [0] * (self.n + 1)
        for i, num in enumerate(nums):
            self.update(i + 1, num)

    def update(self, i, k):
        """

        Args:
            i: 指的是更新数组中的第几个数，对应索引是i-1
            k: 更新的数值

        """
        while i <= self.n:
            self.tree[i] += k
            i += (i & -i)

    def getSum(self, i):
        """

        Args:
            i: 返回前几个数的前缀和

        Returns: 前i个数的前缀和

        """
        s = 0
        while i:
            s += self.tree[i]
            i -= (i & -i)
        return s


def main():
    nums = [1, 2, 3, 4]
    tree = BITree(nums)
    # 打印前1,2,3,4个数的前缀和
    print(tree.getSum(1))
    print(tree.getSum(2))
    print(tree.getSum(3))
    print(tree.getSum(4))
    # 更新第2个数的值，增加3
    tree.update(2, 3)
    # 再次打印前1,2,3,4个数的前缀和
    print(tree.getSum(1))
    print(tree.getSum(2))
    print(tree.getSum(3))
    print(tree.getSum(4))
    # 更新第2个数的值，减少3
    tree.update(2, -3)
    print(tree.getSum(1))
    print(tree.getSum(2))
    print(tree.getSum(3))
    print(tree.getSum(4))


if __name__ == '__main__':
    main()

Output:

1
2
Sum of elements in arr[0..5] is 12
Sum of elements in arr[0..5] after update is 18

Can we extend the Binary Indexed Tree to computing the sum of a range in O(Logn) time? Yes. rangeSum(l, r) = getSum(r) – getSum(l-1).

Applications: The implementation of the arithmetic coding algorithm.

典型题目

leetcode 315 计算右侧小于当前元素的个数

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例：

输入：[5,2,6,1] 输出：[2,1,1,0] 解释： 5 的右侧有 2 个更小的元素 (2 和 1) 2 的右侧仅有 1 个更小的元素 (1) 6 的右侧有 1 个更小的元素 (1) 1 的右侧有 0 个更小的元素

链接：https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self

树状数组解法，用每个数的rank来离散化，反序插入树状数组中，前一位的前缀和就是右侧小于当前元素的个数。

示例代码如下：

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
class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        rank = {val: i + 1 for i, val in enumerate(sorted(nums))}
        n = len(nums)
        res = []

        BITree = [0] * (n + 1)

        def update(i, k=1):
            while i <= n:
                BITree[i] += k
                i += i & -i

        def getSum(i):
            s = 0
            while i:
                s += BITree[i]
                i -= i & -i
            return s

        for num in reversed(nums):
            res.append(getSum(rank[num] - 1))
            update(rank[num])

        return res[::-1]

发表于 更新于 Valine：

参考：

https://www.geeksforgeeks.org/interval-tree/

https://stackoverflow.com/questions/17466218/what-are-the-differences-between-segment-trees-interval-trees-binary-indexed-t#:~:text=Segment%20tree%20stores%20intervals%2C%20and,with%20a%20given%20interval%22%20queries.

实际问题（简单记，类似于点的添加和删除和查找，都要快速，点的解决办法是平衡BST，使得这几种操作都变成O(logn)，区间的添加删除类似，查找的是overlap，这时就需要用到区间树）

Consider a situation where we have a set of intervals and we need following operations to be implemented efficiently. 1) Add an interval 2) Remove an interval 3) Given an interval x, find if x overlaps with any of the existing intervals.

考虑我们有一个集合的区间，并且我们需要以下操作能够有效率的实现：

  1. 添加一个区间
  2. 删除一个区间
  3. 对于一个给定的区间x，找出x是否有和任意一个已经存在的区间有重合。

Interval Tree: The idea is to augment a self-balancing Binary Search Tree (BST) like Red Black Tree, AVL Tree, etc to maintain set of intervals so that all operations can be done in O(Logn) time.

Every node of Interval Tree stores following information. a) i: An interval which is represented as a pair [low, high] b) max: Maximum high value in subtree rooted with this node.

区间的最小值用作BST的键值来保持BST的顺序。那么插入和删除就和自平衡BST的插入删除一样。

那么我们就来看找重合区间的操作。

Following is algorithm for searching an overlapping interval x in an Interval tree rooted with root.

1
2
3
4
5
6
7
Interval overlappingIntervalSearch(root, x)
1) If x overlaps with root's interval, return the root's interval.

2) If left child of root is not empty and the max  in left child 
is greater than x's low value, recur for left child

3) Else recur for right child.

How does the above algorithm work? Let the interval to be searched be x. We need to prove this in for following two cases.

Case 1: When we go to right subtree, one of the following must be true. a) There is an overlap in right subtree: This is fine as we need to return one overlapping interval. b) There is no overlap in either subtree: We go to right subtree only when either left is NULL or maximum value in left is smaller than x.low. So the interval cannot be present in left subtree.

Case 2: When we go to left subtree, one of the following must be true. a) There is an overlap in left subtree: This is fine as we need to return one overlapping interval. b) There is no overlap in either subtree: This is the most important part. We need to consider following facts. … We went to left subtree because x.low <= max in left subtree …. max in left subtree is a high of one of the intervals let us say [a, max] in left subtree. …. Since x doesn’t overlap with any node in left subtree x.low must be smaller than ‘a‘. …. All nodes in BST are ordered by low value, so all nodes in right subtree must have low value greater than ‘a‘. …. From above two facts, we can say all intervals in right subtree have low value greater than x.low. So x cannot overlap with any interval in right subtree.

Applications of Interval Tree: Interval tree is mainly a geometric data structure and often used for windowing queries, for instance, to find all roads on a computerized map inside a rectangular viewport, or to find all visible elements inside a three-dimensional scene (Source Wiki).

Interval Tree vs Segment Tree Both segment and interval trees store intervals. Segment tree is mainly optimized for queries for a given point, and interval trees are mainly optimized for overlapping queries for a given interval.

区间树和线段树都是存储区间的，不同的是线段是针对给定点的查询进行优化，区间树针对给定区间的重叠查询进行优化。

发表于 更新于 Valine：

参考：

https://zh.wikipedia.org/wiki/%E7%B7%9A%E6%AE%B5%E6%A8%B9

https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/

原文我觉得挺不错的，暂时觉得先不翻译。

链接

实际问题（简单记，想快速知道数组的某一区间和，同时数组的修改频繁，使得这两种操作都变成O(logn)，用线段树，可利用思想解决最大子段和问题）

Let us consider the following problem to understand Segment Trees.

We have an array arr[0 . . . n-1]. We should be able to 1 Find the sum of elements from index l to r where 0 <= l <= r <= n-1

2 Change value of a specified element of the array to a new value x. We need to do arr[i] = x where 0 <= i <= n-1.

A simple solution is to run a loop from l to r and calculate the sum of elements in the given range. To update a value, simply do arr[i] = x. The first operation takes O(n) time and the second operation takes O(1) time.

Another solution is to create another array and store sum from start to i at the ith index in this array. The sum of a given range can now be calculated in O(1) time, but update operation takes O(n) time now. This works well if the number of query operations is large and very few updates.

给定一个数组，我们既想快速的知道任意一段区间的总和是多少，也想经常改变其中任何一个元素的值。

第一种解决办法就是，对每一个l和r，我们计算l和r之间的和，O(n)的复杂度，改变其中任何一个值，O(1)的时间复杂度。

第二种解决办法就是，我们创建好另一个数组，存储从开始到这个索引的元素和是多少，（前缀和，通常前缀和在数组的前面加上一个0，这样所有lr之间的和等于这个_sum数组的 _sum[r] - _sum[l-1]）。这样求l到r之间的和就变成O(1)的时间复杂度了，但是每改变一个值就变成O(n)的了。

What if the number of query and updates are equal? Can we perform both the operations in O(log n) time once given the array? We can use a Segment Tree to do both operations in O(Logn) time.

Representation of Segment trees 1. Leaf Nodes are the elements of the input array. 2. Each internal node represents some merging of the leaf nodes. The merging may be different for different problems. For this problem, merging is sum of leaves under a node.

An array representation of tree is used to represent Segment Trees. For each node at index i, the left child is at index 2i+1, right child at 2i+2 and the parent is at st1.

How does above segment tree look in memory? Like Heap, the segment tree is also represented as an array. The difference here is, it is not a complete binary tree. It is rather a full binary tree (every node has 0 or 2 children) and all levels are filled except possibly the last level. Unlike Heap, the last level may have gaps between nodes. Below are the values in the segment tree array for the above diagram.

Below is memory representation of segment tree for input array {1, 3, 5, 7, 9, 11} st[] = {36, 9, 27, 4, 5, 16, 11, 1, 3, DUMMY, DUMMY, 7, 9, DUMMY, DUMMY}

The dummy values are never accessed and have no use. This is some wastage of space due to simple array representation. We may optimize this wastage using some clever implementations, but code for sum and update becomes more complex.

Construction of Segment Tree from given array We start with a segment arr[0 . . . n-1]. and every time we divide the current segment into two halves(if it has not yet become a segment of length 1), and then call the same procedure on both halves, and for each such segment, we store the sum in the corresponding node. All levels of the constructed segment tree will be completely filled except the last level. Also, the tree will be a Full Binary Tree because we always divide segments in two halves at every level. Since the constructed tree is always a full binary tree with n leaves, there will be n-1 internal nodes. So the total number of nodes will be 2*n – 1. Note that this does not include dummy nodes.

What is the total size of the array representing segment tree? If n is a power of 2, then there are no dummy nodes. So the size of the segment tree is 2n-1 (n leaf nodes and n-1) internal nodes. If n is not a power of 2, then the size of the tree will be 2*x – 1 where x is the smallest power of 2 greater than n. For example, when n = 10, then size of array representing segment tree is 2*16-1 = 31. An alternate explanation for size is based on heignt. Height of the segment tree will be st2. Since the tree is represented using array and relation between parent and child indexes must be maintained, size of memory allocated for segment tree will be st3.

Query for Sum of given range Once the tree is constructed, how to get the sum using the constructed segment tree. The following is the algorithm to get the sum of elements.

1
2
3
4
5
6
7
8
9
10
int getSum(node, l, r) 
{
   if the range of the node is within l and r
        return value in the node
   else if the range of the node is completely outside l and r
        return 0
   else
    return getSum(node's left child, l, r) + 
           getSum(node's right child, l, r)
}

Update a value Like tree construction and query operations, the update can also be done recursively. We are given an index which needs to be updated. Let diff be the value to be added. We start from the root of the segment tree and add diff to all nodes which have given index in their range. If a node doesn’t have a given index in its range, we don’t make any changes to that node.

Implementation: Following is the implementation of segment tree. The program implements construction of segment tree for any given array. It also implements query and update operations.

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
# Python3 program to show segment tree operations like 
# construction, query and update 
from math import ceil, log2; 

# A utility function to get the 
# middle index from corner indexes. 
def getMid(s, e) : 
   return s + (e -s) // 2; 

""" A recursive function to get the sum of values 
   in the given range of the array. The following 
   are parameters for this function. 

  st --> Pointer to segment tree 
    si --> Index of current node in the segment tree. 
     Initially 0 is passed as root is always at index 0 
   ss & se --> Starting and ending indexes of the segment 
                represented by current node, i.e., st[si] 
    qs & qe --> Starting and ending indexes of query range """
def getSumUtil(st, ss, se, qs, qe, si) : 

    # If segment of this node is a part of given range, 
 # then return the sum of the segment 
    if (qs <= ss and qe >= se) : 
     return st[si]; 

    # If segment of this node is 
    # outside the given range 
   if (se < qs or ss > qe) : 
        return 0; 

 # If a part of this segment overlaps 
    # with the given range 
  mid = getMid(ss, se); 
    
  return getSumUtil(st, ss, mid, qs, qe, 2 * si + 1) + \ 
      getSumUtil(st, mid + 1, se, qs, qe, 2 * si + 2); 

""" A recursive function to update the nodes 
which have the given index in their range. 
The following are parameters st, si, ss and se 
are same as getSumUtil() 
i --> index of the element to be updated. 
    This index is in the input array. 
diff --> Value to be added to all nodes 
which have i in range """
def updateValueUtil(st, ss, se, i, diff, si) : 

 # Base Case: If the input index lies 
    # outside the range of this segment 
 if (i < ss or i > se) : 
      return; 

   # If the input index is in range of this node, 
  # then update the value of the node and its children 
    st[si] = st[si] + diff; 
  
  if (se != ss) : 
 
      mid = getMid(ss, se); 
        updateValueUtil(st, ss, mid, i, 
                      diff, 2 * si + 1); 
       updateValueUtil(st, mid + 1, se, i, 
                      diff, 2 * si + 2); 

# The function to update a value in input array 
# and segment tree. It uses updateValueUtil() 
# to update the value in segment tree 
def updateValue(arr, st, n, i, new_val) : 

    # Check for erroneous input index 
   if (i < 0 or i > n - 1) : 
        
      print("Invalid Input", end = ""); 
        return; 

   # Get the difference between 
    # new value and old value 
   diff = new_val - arr[i]; 

   # Update the value in array 
 arr[i] = new_val; 

  # Update the values of nodes in segment tree 
    updateValueUtil(st, 0, n - 1, i, diff, 0); 

# Return sum of elements in range from 
# index qs (quey start) to qe (query end). 
# It mainly uses getSumUtil() 
def getSum(st, n, qs, qe) : 

  # Check for erroneous input values 
  if (qs < 0 or qe > n - 1 or qs > qe) : 

     print("Invalid Input", end = ""); 
        return -1; 
  
  return getSumUtil(st, 0, n - 1, qs, qe, 0); 

# A recursive function that constructs 
# Segment Tree for array[ss..se]. 
# si is index of current node in segment tree st 
def constructSTUtil(arr, ss, se, st, si) : 

   # If there is one element in array, 
 # store it in current node of 
   # segment tree and return 
   if (ss == se) : 
 
      st[si] = arr[ss]; 
        return arr[ss]; 
 
  # If there are more than one elements, 
  # then recur for left and right subtrees 
    # and store the sum of values in this node 
  mid = getMid(ss, se); 
    
  st[si] = constructSTUtil(arr, ss, mid, st, si * 2 + 1) +\ 
            constructSTUtil(arr, mid + 1, se, st, si * 2 + 2); 
   
  return st[si]; 

""" Function to construct segment tree 
from given array. This function allocates memory 
for segment tree and calls constructSTUtil() to 
fill the allocated memory """
def constructST(arr, n) : 

 # Allocate memory for the segment tree 

    # Height of segment tree 
    x = (int)(ceil(log2(n))); 

  # Maximum size of segment tree 
  max_size = 2 * (int)(2**x) - 1; 
  
  # Allocate memory 
   st = [0] * max_size; 

   # Fill the allocated memory st 
  constructSTUtil(arr, 0, n - 1, st, 0); 

 # Return the constructed segment tree 
   return st; 

# Driver Code 
if __name__ == "__main__" : 

    arr = [1, 3, 5, 7, 9, 11]; 
   n = len(arr); 

  # Build segment tree from given array 
   st = constructST(arr, n); 

  # Print sum of values in array from index 1 to 3 
    print("Sum of values in given range = ", 
                   getSum(st, n, 1, 3)); 

  # Update: set arr[1] = 10 and update 
    # corresponding segment tree nodes 
  updateValue(arr, st, n, 1, 10); 

    # Find sum after the value is updated 
   print("Updated sum of values in given range = ", 
                   getSum(st, n, 1, 3), end = "");

Output:

1
2
Sum of values in given range = 15
Updated sum of values in given range = 22

Time Complexity: Time Complexity for tree construction is O(n). There are total 2n-1 nodes, and value of every node is calculated only once in tree construction.

Time complexity to query is O(Logn). To query a sum, we process at most four nodes at every level and number of levels is O(Logn).

The time complexity of update is also O(Logn). To update a leaf value, we process one node at every level and number of levels is O(Logn).

示例题目

  1. SPOJ-GSS1

    You are given a sequence A[1], A[2], ..., A[N] . ( |A[i]| ≤ 15007 , 1 ≤ N ≤ 50000 ). A query is defined as follows: Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y }. Given M queries, your program must output the results of these queries.

    Input

    • The first line of the input file contains the integer N.
    • In the second line, N numbers follow.
    • The third line contains the integer M.
    • M lines follow, where line i contains 2 numbers xi and yi.

    Output

    Your program should output the results of the M queries, one query per line.

    Example

    1
    2
    3
    4
    5
    6
    7
    8
    Input:
    3 
    -1 2 3
    1
    1 2

    Output:
    2

大致翻译：给定一段长度为n的序列a1, a2, ..., an （a有正有负），每次询问[L, R] (即aL ~ aR)范围内的最大子段和，并涉及单点修改操作。

线段树：维护区间最大子段和。

这里不能用传统的线段树了，我们维护的值要更多。

  1. 定义：

    线段树一共要维护4个值，如下：（每个值的含义都是相对于该结点对应区间[l, r]而言）

    1
    2
    3
    4
    5
    6
    7
    8
    struct node
    {
        int sum;       //[l,r]区间之和
        int max_sum;   //[l,r]内的最大子段和
        int max_pre;   //[l,r]内的最大前缀和
        int max_post;  //[l,r]内的最大后缀和
    }t[maxn<<2];

    1. 向上传递

    我们采用分治归并的思路，我们知道在l=r时这四个值都是确定的，都等于al。那么通过左右两边的四个值如何求出合并后的值呢。这里我觉得这段话讲的很清楚。

    我们定义一个操作get(a, l, r)表示查询a序列[l, r]区间内的最大子段和。如何分治实现这个操作呢？对于一个区间l, r，我们取m = (l + r)/2， 对区间[l,m] 和 [m+1, r]分治求解。当递归逐层深入直到区间长度缩小为1的时候，递归「开始回升」。这个时候我们考虑如何通过[l, m]区间的信息和[m+1, r]区间的信息合并成区间[l, r]的信息。最关键的两个问题是：

    • 我们要维护区间的哪些信息呢？
    • 我们如何合并这些信息？

    对于一个区间[l, r]，我们可以维护四个量：

    • lSum表示[l, r]内以l为左端点的最大子段和
    • rSum表示[l, r]内以r为右端点的最大字段和
    • mSum表示[l, r]内的最大子段和
    • iSum表示[l, r]的区间和

    以下简称[l, m]为[l, r]的「左子区间」，[m+1, r]为[l, r]的右子区间。我们考虑如何维护这些量呢（如何通过左右子区间的信息合并得到[l,r]的信息）？对于长度为1的区间[i,i]，四个量的值都和ai相等。对于长度大于1的区间：

    首先最好维护的是iSum，区间[l, r]的iSum就等于「左子区间」的iSum加上「右子区间」的iSum。

    对于[l, r]的lSum，存在两种可能，它要么等于「左子区间」的lSum，要么等于「左子区间」的iSum加上「右子区间」的lSum，两者取大。

    对于[l, r]的rSum，同理，它要么等于「右子区间」的rSum，要么等于「右子区间」的iSum加上「左子区间」的rSum，两者取大。

    当计算好上面的三个量之后，就很好计算[l, r]的mSum了。我们可以考虑[l, r]的mSum对应的区间是否跨越m--它可能不跨越m，也就是说[l, r]的mSum可能是「左子区间」的mSum和「右子区间」的mSum中的一个；它可能跨越m，可能是「左子区间」的rSum和「右子区间」的lSum求和。三者取大。

    我们把这个过程叫做向上传递，英文叫做pushup。

    如果我们把 [0,n−1] 分治下去出现的所有子区间的信息都用堆式存储的方式记忆化下来，即建成一颗真正的树之后，我们就可以在 O(logn) 的时间内求到任意区间内的答案，我们甚至可以修改序列中的值，做一些简单的维护，之后仍然可以在 O(logn) 的时间内求到任意区间内的答案，对于大规模查询的情况下，这种方法的优势便体现了出来。这棵树就是线段树。

  2. leetcode，53. 最大子序和，可用dp也可用线段树求解。与上一题一样，只不过上一题有多个query，适合把线段树存下来。

    示例解法：

    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
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    # 线段树
    # 我们定义一个操作get(a, l, r)表示查询a序列[l, r]区间内的最大子段和，
    # 那么最终我们要求的答案就是get(arr, 0, n-1)。如何分治实现这个操作呢？
    # 对于一个区间l, r，我们取m = (l + r)/2， 对区间[l,m] 和 [m+1, r]分治求解。
    # 当递归逐层深入直到区间长度缩小为1的时候，递归「开始回升」。
    # 这个时候我们考虑如何通过[l, m]区间的信息和[m+1, r]区间的信息合并成区间[l, r]的信息。
    # 最关键的两个问题是：
    # 我们要维护区间的哪些信息呢？
    # 我们如何合并这些信息？
    # 对于一个区间[l, r]，我们可以维护四个量：
    # lSum表示[l, r]内以l为左端点的最大子段和
    # rSum表示[l, r]内以r为右端点的最大字段和
    # mSum表示[l, r]内的最大子段和
    # iSum表示[l, r]的区间和
    # 以下简称[l, m]为[l, r]的「左子区间」，[m+1, r]为[l, r]的右子区间。
    # 我们考虑如何维护这些量呢（如何通过左右子区间的信息合并得到[l,r]的信息）？
    # 对于长度为1的区间[start,start]，四个量的值都和ai相等。对于长度大于1的区间：
    # 首先最好维护的是iSum，区间[l, r]的iSum就等于「左子区间」的iSum加上「右子区间」的iSum。
    # 对于[l, r]的lSum，存在两种可能，它要么等于「左子区间」的lSum，
    # 要么等于「左子区间」的iSum加上「右子区间」的lSum，两者取大。
    # 对于[l, r]的rSum，同理，它要么等于「右子区间」的rSum，
    # 要么等于「右子区间」的iSum加上「左子区间」的rSum，两者取大
    # 当计算好上面的三个量之后，就很好计算[l, r]的mSum了。
    # 我们可以考虑[l, r]的mSum对应的区间是否跨越m--它可能不跨越m，
    # 也就是说[l, r]的mSum可能是「左子区间」的mSum和「右子区间」
    # 的mSum中的一个；
    # 它可能跨越m，可能是「左子区间」的rSum和「右子区间」的lSum求和。三者取大。
    # 时间复杂度，相当于遍历一个二叉树的所有结点，结点最多为2*n个，所以时间为O(n)
    # 空间复杂度：递归：O(logn)
    class Solution:
        def maxSubArray(self, nums: List[int]) -> int:
            l, r = 0, len(nums) - 1
            return self.get(nums, l, r)[2]

        def get(self, nums, l, r):
            if l == r:
                return [nums[l]] * 4

            mid = l + ((r - l) >> 1)
            lSum1, rSum1, mSum1, iSum1 = self.get(nums, l, mid)
            lSum2, rSum2, mSum2, iSum2 = self.get(nums, mid + 1, r)
            iSum = iSum1 + iSum2
            lSum = max(lSum1, iSum1 + lSum2)
            rSum = max(rSum2, iSum2 + rSum1)
            mSum = max(mSum1, mSum2, rSum1 + lSum2)
            return lSum, rSum, mSum, iSum


    # 存储一颗线段树
    class Solution:
        def maxSubArray(self, nums: List[int]) -> int:
            l, r = 0, len(nums) - 1
            memo = {}
            res = self.build(nums, l, r, memo)[2]
            print(memo)
            return res

        def build(self, nums, l, r, memo):
            if l == r:
                memo[l, r] = [nums[l]] * 4
                return [nums[l]] * 4

            mid = l + ((r - l) >> 1)
            lSum1, rSum1, mSum1, iSum1 = self.build(nums, l, mid, memo)
            lSum2, rSum2, mSum2, iSum2 = self.build(nums, mid + 1, r, memo)
            iSum = iSum1 + iSum2
            lSum = max(lSum1, iSum1 + lSum2)
            rSum = max(rSum2, iSum2 + rSum1)
            mSum = max(mSum1, mSum2, rSum1 + lSum2)
            memo[l, r] = [lSum, rSum, mSum, iSum]
            return lSum, rSum, mSum, iSum


    # f(i) s[:i]的最大子序和，且一定包括i
    # f(i) = max(f(i-1), 0) + a[i]
    class Solution:
        def maxSubArray(self, nums: List[int]) -> int:
            pre, cur = float('-inf'), float('-inf')
            for n in nums:
                pre = max(pre + n, n)
                cur = max(cur, pre)
            return cur


    # 「方法二」相较于「方法一」来说，时间复杂度相同，但是因为使用了递归，并且维护了四个信息的结构体，
    # 运行的时间略长，空间复杂度也不如方法一优秀，而且难以理解。
    # 那么这种方法存在的意义是什么呢？
    #
    # 对于这道题而言，确实是如此的。但是仔细观察「方法二」，它不仅可以解决区间 [0,n−1]，
    # 还可以用于解决任意的子区间 [l,r] 的问题。
    # 如果我们把 [0,n−1] 分治下去出现的所有子区间的信息都用堆式存储的方式记忆化下来，
    # 即建成一颗真正的树之后，我们就可以在 O(logn) 的时间内求到任意区间内的答案，
    # 我们甚至可以修改序列中的值，做一些简单的维护，
    # 之后仍然可以在 O(logn) 的时间内求到任意区间内的答案，
    # 对于大规模查询的情况下，这种方法的优势便体现了出来。
    # 这棵树就是上文提及的一种神奇的数据结构——线段树。

发表于 更新于 Valine：

原文

https://www.cs.utexas.edu/~EWD/transcriptions/EWD03xx/EWD340.html

原文很长，这里摘录总结的内容。

摘录

让我结束发言。自动计算机已经陪伴我们四分之一个世纪。它们作为工具的能力对我们的社会产生了巨大的影响，但就这种能力而言，它们的影响只是我们文化表面上的一个涟漪，而与之相比，它们在人类文化史上前所未有的智力挑战能力方面将产生更深远的影响。层次系统似乎具有这样的特性：在一个层次上被视为无法分隔的东西，在下一个层次上被视为更详细的复合对象；因此，当我们把注意力从一个层次转移到下一个更低层次上时，适用于每个层次的自然空间或时间的颗粒就会减少一个数量级。我们用砖头来理解墙壁，用晶体来理解砖头，用分子来理解晶体等等。在一个层次系统中，可以有意义的区分的层次数量，有点正比于最大和最小的晶粒之间的比例的对数，因此，除非这个比例非常大，否则我们不能期望有很多次的层次。在计算机编程中，我们的基本构建的相关时间最小度量不到一微秒，但我们的程序可能需要几个小时的计算时间。我不知道有其他任何技术覆盖了10的10次方或更高的比例：计算机，凭借其神奇的速度，似乎是第一个为我们提供了一个高度层次化的既可能又必要的环境。这种挑战，即，面对编程任务，是如此的独特，以至于这种新奇的经验可以给我们很多关于自己的启示。它应该加深我们对设计和创造过程的理解，它应该让我们更好的控制组织思想的任务。如果它没有做到这一点，以我的品味，我们应该根本不配拥有电脑！

它已经给了我们一些教训，我选择在这次演讲中强调的是以下几点。只要我们在处理任务时充分认识到它的巨大困难，只要我们坚持使用适度而优雅的编程语言，只要我们尊重人类思维的内在局限性，并以非常谦逊的程序员的身份处理任务，我们就会把编程工作做得更好。

ACM Turing Lecture 1972

发表于 Valine：

一句话

当一个进程申请使用资源的时候，银行家算法通过先试探分配给该进程资源，然后通过安全性算法判断分配后的系统是否处于安全状态，若不安全则试探分配作废，让该进程继续等待。

那么此时会有一个问题，如何判断系统是否处于安全状态？算法流程将用下面一张图来表示。

一张图

  • 首先是银行家算法中的进程：

    • 包含进程Pi的需求资源数量（也是最大需求资源数量，MAX）

    • 已分配给该进程的资源A（Allocation）

    • 还需要的资源数量N（Need= M - A）

  • Available为空闲资源数量，即资源池（注意：资源池的剩余资源数量+已分配给所有进程的资源数量=系统中的资源总量）

假设进程P1申请资源，银行家算法先试探的分配给它（当然先要看看当前资源池中的资源数量够不够），若申请的资源数量小于等于Available，然后接着判断分配给P1后剩余的资源，能不能使进程队列的某个进程执行完毕，若没有进程可执行完毕，则系统处于不安全状态（即此时没有一个进程能够完成并释放资源，随时间推移，系统终将处于死锁状态）。

若有进程可执行完毕，则假设回收已分配给它的资源（剩余资源数量增加），把这个进程标记为可完成，并继续判断队列中的其他进程，若所有进程都可执行完毕，则系统处于安全状态，并根据可完成进程的分配顺序生成安全序列（如{P0, P3, P2, P1}表示将申请后的剩余资源Work先分配给P0 -> 回收（Work+已分配给P0的A0=Work） -> 分配给P3 -> 回收（Work + A3 = Work）-> 分配给P2 -> ...... 满足所有进程）。

如此就可避免系统存在潜在死锁的风险。

来个例子

在银行家算法中，若出现下述资源分配情况：

注：题中共四种资源，P0的Allocation为（0，0， 3， 2）表示已分配给P0的第一种资源和第二种资源为0个，第三种资源3个，第四种资源2个。

  1. 该状态是否安全？

  2. 若进程P2提出请求Request（1，2，2，2）后，系统能否将资源分配给它？

  3. 利用安全性算法对上面的状态进行分析（见下表），找到一个安全序列{P0, P3, P4, P1, P2}，故系统是安全的。

  4. P2发出请求向量Request(1,2,2,2)，系统按银行家算法进行检查:

    1. Request2(1,2,2,2) <= Need2(2,3,5,6)

    2. Request2(1,2,2,2) <= Available(1,6,2,2)

    3. 系统先假定可为P2分配资源，并修改Available，Allovation2和Need2向量：

      1. Available = （0，4，0，0）
      2. Allocation2 = （2，5，7，6）
      3. Need2 = （1，1，3，4）

      此时在进行安全检查，发现Available=(0, 4, 0, 0)，不能满足任何一个进程，所以判定系统进入不安全状态，即不能分配给P2相应的Request(1,2,2,2)。

简单伪代码

P - 进程的集合

Mp - 进程p的最大的请求数目

Cp - 进程p当前被分配的资源

A - 当前可用的资源

1
2
3
4
5
6
7
8
9
10
11
12
13
14
while (P != ∅) {
    found = FALSE;
    foreach (p ∈ P) {
            // Mp - Cp就是Need
        if (Mp − Cp ≤ A) {
             /* p可以获得他所需的资源。假设他得到资源后执行；执行终止，并释放所拥有的资源。*/
             A = A + Cp ;
             P = P − {p};
             found = TRUE;
        }
    }
    if (! found) return FAIL;
}
return OK;

发表于 更新于 Valine：

两个问题以及其解答

  1. 问题一：有一个圆形的操场，四周都是墙壁，无法逾越。操场里面有一只老鼠和一只猫，猫在努力的捉老鼠。如果老鼠和猫的奔跑速度一样，那么猫一定能够追到老鼠吗？

    正确的结论正是猫永远也追不上老鼠。

    我们可以通过数学证明证明出，只要老鼠时刻沿着猫的位置到圆心的位置的连线的垂直方向跑，可以证明出永远也不会追上。数学证明见https://zhuanlan.zhihu.com/p/80701068。

  2. 在一个圆形池塘中有一只老鼠，池塘岸边有一只不会游泳的猫。这只老鼠游泳的速度比猫在岸上奔跑的速度要小，但其在岸上奔跑的速度却大于猫的速度。所以，只要老鼠能够在猫还没跑过来的时候游到岸边，那么老鼠就得救了。问，猫的奔跑速度要至少是老鼠游泳速度的多少倍，才能确保抓得住老鼠？

    这道问题的一个简单问法是，假如猫在岸上的速度时老鼠游泳的4倍，那么猫能抓到老鼠吗？

    答案是不能。

    我们可以这么想，老鼠只要在小于1/4r处做绕圆心的圆运动，猫就跟不上老鼠，最终老鼠和猫和圆心会在一条直线上，圆心在老鼠和猫的中间。

    这时候只要老鼠沿着这条直线向远离猫的圆周跑去，假设老鼠的位置距离圆心为x，那么只要

    \[ \frac{r-x}{v_{老鼠}} < \frac{\pi r}{v_{猫}} \]

    老鼠就会比猫先到岸边，这时猫就再也抓不到老鼠了。

    根据猫的速度是老鼠的4倍，

    \[ x = \frac{4-\pi}{4}r \approx0.2146r \]

    所以，只要老鼠在0.2146r到0.25r之间，走到和猫与圆心呈一条直线的位置，猫和老鼠分别在圆心两侧，老鼠往远离猫的方向走，就可以走出。

    原问题问猫的最小速度是多少，才能保证抓住老鼠，依然可以看这篇文章的数学推导https://zhuanlan.zhihu.com/p/80701068。

发表于 更新于 Valine：

题目：LeetCode 887. 鸡蛋掉落

你将获得 K 个鸡蛋，并可以使用一栋从 1 到 N 共有 N 层楼的建筑。

每个蛋的功能都是一样的，如果一个蛋碎了，你就不能再把它掉下去。

你知道存在楼层 F ，满足 0 <= F <= N 任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。

每次移动，你可以取一个鸡蛋（如果你有完整的鸡蛋）并把它从任一楼层 X 扔下（满足 1 <= X <= N）。

你的目标是确切地知道 F 的值是多少。

无论 F 的初始值如何，你确定 F 的值的最小移动次数是多少？

示例 1：

输入：K = 1, N = 2 输出：2 解释： 鸡蛋从 1 楼掉落。如果它碎了，我们肯定知道 F = 0 。 否则，鸡蛋从 2 楼掉落。如果它碎了，我们肯定知道 F = 1 。 如果它没碎，那么我们肯定知道 F = 2 。 因此，在最坏的情况下我们需要移动 2 次以确定 F 是多少。 示例 2：

输入：K = 2, N = 6 输出：3 示例 3：

输入：K = 3, N = 14 输出：4

提示：

1 <= K <= 100 1 <= N <= 10000

思路

基本想法

首先，我们可以看到要得到较大的楼层和鸡蛋的答案，小的情况下的结果是有用的分析，这就导致了动态递推。

定义子问题，也就是定义子状态。

我们有两个变量

  • 还有多少可以扔的鸡蛋 i ，(0 <= i <= K)
  • 还剩下几层楼来测试 j ，(i <= j <= N)

结果就是我们子问题

dp[i][j]就是在还有i个鸡蛋，j层楼的时候，我们要得到这个目标楼层所用的最小次数。

DP方程

初始化

1
2
3
dp[1][j] = j, j = 1...N # one egg, check each floor from 1 to j
dp[i][0] = 0, i = 1...K # no floor, no drop needed to get the optimal floor
dp[i][1] = 1, i = 1...K # one floor, only check once

递推方程

为了得到递归关系，我们来考虑一个测试案例。3个鸡蛋和100层楼 对于写一次降落，我可以从1到100中选择楼层，比如我选择25。 这个掉落有2种可能的结果。

  • 蛋碎了，我现在有2个蛋，可以选择的楼层变成了1~24。
  • 鸡蛋仍然安全，我仍然有3个鸡蛋，要选择的楼层变成26~100。

考虑最坏的情况，用上面的dp定义，我们可以把下一次选择楼层25的情况找目标楼层的情况描述成：

dp[3][100] = 1 + max(dp[2][24], dp[3][75])

除了第25层，对于下次抛下，我们也可以选择1到100层其他楼层。每一次抛下都类似于25层的情况。最终的结果将是所有这些可能的下次抛下的楼层的选择的最小值。

dp[3] [100] = min(..., 1 + max(dp[2] [23], dp[3] [76]), 1 + max(dp[2] [24], dp[3] [75]), 1 + max(dp[2] [25], dp[3] [74]), ...) (拿24、25、26举例)

最终的递推方程是： \[ dp[i] [j] = 1 + min(max(dp[i-1] [k-1], dp[i] [j-k]))， k = 1, 2, ...，j \]

暴力解法：

有了刚才的递推公式，暴力解法应该是O(kn^2)时间复杂度

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = [[float('inf')] * (N + 1) for _ in range(K + 1)]
        for i in range(1, K + 1):
            dp[i][0] = 0
            dp[i][1] = 1
        for j in range(1, N + 1):
            dp[1][j] = j

        for i in range(2, K + 1):
            for j in range(2, N + 1):
                for k in range(1, j + 1):
                    dp[i][j] = min(dp[i][j],
                                   1 + max(dp[i - 1][k - 1], dp[i][j - k]))
        return dp[K][N]

或者减少空间复杂度的下面代码

1
2
3
4
5
6
7
8
9
10
class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = list(range(N + 1))
        _dp = [0] * (N + 1)
        for _ in range(K - 1):
            for j in range(1, N + 1):
                _dp[j] = 1 + min(max(dp[k - 1], _dp[j - k])
                                 for k in range(1, j + 1))
            dp, _dp = _dp, dp
        return dp[N]

优化1，对每个dp[i] [j]选择k

我们的暴力解法在leetcode上超时了，提示我们要检查for循环中不必要的迭代。更具体的说，为了得到每次抛下最适合的k值，我们不需要遍历从i到j的所有楼层， dp[i] [k]是一个随k的升高而升高的函数。这意味着dp[i-1] [k-1]将会升高而dp[i] [j-k]将会降低，当k从1到j的时候。最优的k值将在中点这两个值相遇的时候。所以为了得到最优的k值，我们可以对k从1到j做一个二分搜索。

这将使得第三个对k循环从O(n)的时间复杂度下降到O(logn)。总时间复杂度是O(knlogn)。使用二分搜索，我们只能做自底向上的dp，示例代码如下：

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
class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        def dfs(i, j):
            if i == 1:
                return j
            if j == 0:
                return 0
            if j == 1:
                return 1
            if (i, j) in d:
                return d[i, j]
            lo, hi = 0, j
            while lo < hi:
                mid = (lo + hi) / 2
                left, right = dfs(i - 1, mid - 1), dfs(i, j - mid)
                if left < right:
                    lo = mid + 1
                else:
                    hi = mid
            res = 1 + max(dfs(i - 1, lo - 1), dfs(i, j - lo))
            d[i, j] = res
            return res

        d = {}
        return dfs(K, N)

优化2，为每个dp[i] [1..N] 选择 k_1 .. k_N

再进一步，到现在为止，我们仍然在为了每个dp[i] [j]寻找从1到j的最优层数k。事实上，我们可以看到，随着j的增加，每个dp[i] [j]的最优楼层k也在增加。这意味着一旦我们得到了dp[i] [j]的最优k，我们就可以保存当前k值，直接开始下一轮的for-loop，而不用再从0开始启动k。这样，在第三个for-loop中，由于j在第二个for-loop中从1到N，k只会从1到N一次，总的时间复杂度为O(kN)。代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = [[float('inf')] * (N + 1) for _ in range(K + 1)]
        for i in range(1, K + 1):
            dp[i][0] = 0
            dp[i][1] = 1
        for j in range(1, N + 1):
            dp[1][j] = j

        for i in range(2, K + 1):
            k = 1
            for j in range(2, N + 1):
                while k < j + 1 and dp[i][j - k] > dp[i - 1][k - 1]:
                    k += 1
                dp[i][j] = 1 + dp[i - 1][k - 1]
        return dp[K][N]

优化3，空间复杂度

通常情况下，如果dp的递归关系是基于之前状态的恒定长度，我们可以节省一个维度的空间复杂度。在这里，当前行dp[i]是基于当前行和前行得到更新的，所以我们可以只记录这两行，并在迭代过程中进行更新，以节省一维的空间复杂度。最终时间复杂度O(kn)，空间复杂度O(n)。代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = range(N + 1)
        for i in range(2, K + 1):
            k = 1
            ndp = [0, 1] + [float('inf')] * (N - 1)
            for j in range(2, N + 1):
                while k < j + 1 and ndp[j - k] > dp[k - 1]:
                    k += 1
                ndp[j] = 1 + dp[k - 1]
            dp = ndp
        return dp[N]

优化代码：

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
# f(i, j)还剩i个鸡蛋，k层楼，最少需要的次数
# 距离f(2, 100) 2个鸡蛋100层楼
# 选了25层，碎了，没碎
#        max(f(i-1, k-1) , f(i, j-k))
# f(i, j) = min(max(f(i-1, k-1), f(i, j-k))) + 1 for k in 1..j
# 初始化和边界条件
# f(i,1) = 1,一层只需要一次，只要鸡蛋数大于等于1
# f(1,j) = j,一个鸡蛋只能从最低层一个一个实验
# 层数加上一个哨兵0，这样访问索引即是层数，并且当k等于1时，递推到f(i, 0)为0
# 在一层碎了，f(i, 0) = 0
# 返回值，f(K,N)
# 优化复杂度
# 我们的k不用从1开始，随着j的增加，最合适的k层也是在增加的，对于每一个i，我们都重新开始计k
# 在这一轮中，k从上一次最佳开始，最佳的时候f(i-1, k-1) >= f(i, j-k)
# 我们取f(i-1, k-1)，更新f(i, j) = f(i-1,k-1)+1
# 可降低时间复杂度为O(KN)
# 空间复杂度，我们可以使用两个数组滚动
# 一个代表i-1个鸡蛋时，一个表示i个鸡蛋时
class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        dp = list(range(N + 1))
        ndp = [0] * (N + 1)
        for i in range(2, K + 1):
            k = 1
            for j in range(1, N + 1):
                while k <= j and dp[k - 1] < ndp[j - k]:
                    k += 1
                ndp[j] = dp[k - 1] + 1
            dp, ndp = ndp, dp
        return dp[N]

总结

我个人建议按照以下逻辑来思考这个问题。

  1. 为什么要用dp？在什么情况下我们应该用dp来解决问题？
  2. 问题中描述一个状态的基本情况和递归关系是什么？
  3. 根据以上分析，dp公式是什么？
  4. 实现蛮力解决。
  5. 优化：找到dp数组的模式，哪些迭代是不必要的，可以节省的？
  6. 时间和空间复杂度是多少？有什么办法可以节省一个维度的空间复杂度？

转载感谢

感谢优秀题解

https://leetcode.com/problems/super-egg-drop/discuss/159079/Python-DP-from-kn2-to-knlogn-to-kn

发表于 更新于 Valine：

参考：

https://blog.csdn.net/longzw0/article/details/66970832

代码的未来–松本行弘

https://medium.com/@NTulswani/understanding-and-implementing-a-garbage-collector-a19afb1bc418， 标记清除js代码简单实现

将内存管理，尤其是内存空间的释放实现自动化，这就是GC（Garbage Collection）。

GC是一个很古老的技术，从20世纪60年代就开始研究，还发表了不少论文。这项技术在大学实验室级别的地方已经应用了很长时间，但是可以说从20时间90年代Java出现之后，一般程序员才有缘解除到它，在此之前这项技术还只是少数人的专利。

术语定义

1.垃圾

所谓垃圾（Garbage），就是需要回收的对象。作为编写程序的人，是可以做出“这个对象已经不需要了”这样的判断，但是计算机是做不到的。因此如果程序（通过某个变量等等）可能会直接或间接的引用一个对象，那么这个对象就被视为“存活”；与之相反，已经引用不到的则被视为“死亡”。将这些死亡对象找出来，然后作为垃圾进行回收，这就是GC的本质。

2.根

所谓的根（Root），就是判断对象是否被引用的起始点。至于哪里的才是根，不同的语言和编译器都有不同的规定，但基本上是将变量和运行栈空间作为根。

主要GC实现方式

1.标记清除方式

标记清除（Mark and Sweep）是最早开发出来的GC算法（1960年）。它的原理非常简单：首先从根开始将可能被引用的对象用递归的方式进行标记，然后将没有标记到的对象作为垃圾进行回收。

初始状态：

标记阶段：

清除阶段：

上述图片显示了标记清楚算法的大致原理。

”初始状态“图中显示了随着程序的运行而分配出一些对象的状态，一个对象可以对其他的对象进行引用。

”标记阶段“图中显示了GC开始执行，从根开始可以在被引用的对象上进行”标记“。大多数情况下，这种标记是通过对象内部的标志（Flag）来实现的。于是，被标记的对象我们将它涂黑。

紧接着被标记的对象所能引用的对象也会被打上标记。重复这一步骤就可以从根开始给可能被间接引用到的对象全部打上标记。到此为止的操作即被称为——标记阶段（Mark phase）。标记阶段完成时，被标记的对象就是”存活“对象，反之为”死亡“对象。

标记清除算法的处理时间，是和存活对象数域对象总数的总和相关的。

作为标记清除的变形，还有一种叫做标记压缩（Mark and Compat）的算法，它不是将被标记的对象清除，而是将它们不断压缩。

2.复制收集方式

标记清除算法有一个缺点，就是在分配了大量对象，并且其中只有一小部分存活的情况下，所消耗的时间会大大超过必要的值，这是因为在清除阶段还需要对大量死亡对象进行扫描。

复制收集（Copy and Collection）则试图克服这一缺点。在这种算法中，会将从根开始被引用的对象复制到另外的空间中，然后，在将复制的对象所能够引用的对象用递归的方式不断复制下去。

初始状态（1）——旧空间：

新空间的开辟（2）——新空间：

复制对象（3）

如上图：

（1）部分是GC开始前的内存状态，这也同时代表着对象在内存中所占用的”旧空间“。

（2）在旧空间以外开辟”新空间“并将可能从根被引用的对象复制到新空间中。

（3）从已经复制的对象开始再将可以被引用的对象逐个复制到新空间当中……随着复制的进行，直到复制完成——最终”死亡“对象就留在了”旧空间”当中，接着将旧空间废弃掉，这样就可以将“死亡”对象是哟占用的空间一口气释放出来，而没有必要再次扫描“死亡”对象了。等到下次GC操作时，这次所创建的“新空间”就成为了将来的“旧空间”了。

复制收集方式的过程相当于只存在标记清除方式中的标记阶段。由于清除阶段中需要对所有对象进行扫描，这样如果存在大量对象，且其中大量对象已经为“死亡”对象的情况下必然会造成不必要的资源和性能上的开销。

而在复制收集方式中就不存在这样的开销。但是和标记相比，将对象复制一份的开销相对要大，因此在“存活”对象相对比例较高的请情况下，反而不利。

复制收集方式的另一个优点是：它具有局部性（Locality）。在复制收集的过程中，会按照对象被引用的顺序将对象复制到新空间中。于是，关系较近的对象被放置在距离较近的内存空间中的可能性会提高，这样被称为局部性。局部性高的情况下，内存缓存会更容易有效运作，程序的运行也能够得到提高。

引用计数方式

引用计数方式是GC算法中最简单也最容易实现的一种，它和标记清除方式差不多是同一个时间被发明出来的。

它的原理是：在每个对象中保存该对象的引用计数，当引用发生增减时对计数进行更新。

引用计数的增减，一般发生在变量复制，对象内容更新，函数结束（局部变量不再被引用）等时间点。当一个对象的引用计数为0时，则说明它将来不会再被引用，因此可以释放相应的内存空间。

（1）

（2）

（3）

如上图：

（1）中所有对象都保存着自己被多少个对象进行引用的数量（引用计数）——图中右上角的数字。

（2）当对象引用发生变化时，引用计数也会跟着变化。在这里图中的对象B到D的引用失效后，对象D的引用计数变为0，由于对象D的引用计数变为0，因此D到E和C的引用计数也分别减少。结果E的引用计数也变为0，于是对象E也会被释放。

（3）引用计数为0的对象被释放——“存活”的对象被保留下来。而这个GC过程中不需要对所有对象进行扫描。

优点：

  • 相比标记清除和复制收集方式实现更容易。
  • 当对象不再被引用的瞬间就会被释放。
  • 其他GC机制中，要预测一个对象何时会被释放是很困难的，而在引用计数方式中则是立即被释放。
  • 由于释放操作是针对个别执行的，因此和其他算法相比，由GC而产生的中断时间比较短。

缺点：

  • 无法释放循环引用的对象。如上图A，B，C三个对象没有被其他对象引用，而是互相之间循环引用，因此它们的引用计数永远不会为0，结果这些对象就永远不会被释放。
  • 必须在引用发生增减时对引用计数做出正确的增减，而如果漏掉或者更改了引用计数就会引发很难找到的错误。
  • 引用计数不适合并行处理。如果多个线程同时对引用计数进行增减的话，引用计数的值就可能会产生不一致的问题（结果就会导致内存错误），为了避免这样的事情发生，对引用计数的操作必须采用独占的方式来进行。如果引用计数操作频繁进行，每次使用都要使用加锁等并发操作，其开销也不可小觑。

实际的GC实现会涉及很多优化。

发表于 Valine：

天下没有谁生而知之，都是学而知之。人的学问哪来，您记住，无论谁啊，都算上， 大思想家，大文学家，大作家，也是俩字，记问之学。一个就是看书，《史记》上有这么一句话我把它记下来了，《三国志》有这么句话我把它记下来了。记，还有就是问。这我不懂，哎呦先生您看，这怎么回事。先生告诉你了啊，这个如何如何。所有人的学问，都是这么来的。记问之学，所以要广览多读。

至于发明创造，也需要了解已有知识，还是需要记 与 问。