eleven26

defer 的作用和执行时机

go 的 defer 是用来延迟执行函数的，而且延迟发生在调用函数 return 之后，比如：

1
2
3
4

func a() int {
	defer b()
	return 0
}

b 的执行是发生在 return 0 之后，注意 defer 的语法，关键字 defer 之后是函数的调用。

defer 的重要用途一：清理释放资源

由于 defer 的延迟特性，defer 常用在函数调用结束之后清理相关的资源，比如：

1
2

f, _ := os.Open(filename)
defer f.close()

文件资源的释放会在函数调用结束之后借助 defer 自动运行，不需要时刻记住哪里的资源需要释放，打开和释放必须相对应。

用一个例子深刻诠释一下 defer 带来的便利和简洁。

代码的主要目的是打开一个文件夹，然后复制内容到另一个新的文件中，没有 defer 时这样写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

func CopyFile(dstName, srcName string) (written int64, err error) {
	src, err := os.Open(srcName)
	if err != nil {
		return
	}
	dst, err := os.Create(dstName)
	if err != nil { // 1
		return
	}
	written, err = io.Copy(dst, src)
	dst.Close()
	src.Close()
	return
}

代码在 #1 处返回之后，src 文件没有执行关闭操作，可能会导致资源不能正确释放，改用 defer 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13

func CopyFile(dstName, srcName string) (written int64, err error) {
	src, err := os.Open(srcName)
	if err != nil {
		return
	}
	defer src.Close()
	dst, err := os.Create(dstName)
	if err != nil {
		return
	}
	defer dst.Close()
	return io.Copy(dst, src)
}

这样一来，src 和 dst 都能及时清理和释放，无论 return 在什么地方执行。

鉴于 defer 的这种作用，defer 常用来释放数据库连接，文件打开句柄等释放资源的操作。

defer 的重要用途二：执行 recover

被 defer 的函数在 return 之后执行，这个时机点正好可以捕获函数抛出的 panic，因而 defer 的另一个重要用途就是执行 recover。

recover 只有在 defer 中使用才更有意义，如果在其他地方是使用，由于 program 已经调用结束而提前返回而无法有效捕捉错误。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

package main

import (
	"fmt"
)

func main() {
	defer func() {
		if ok := recover(); ok != nil {
			fmt.Println("recover")
		}
	}()
	panic("error")
}

记住 defer 要放在 panic 执行之前。

多个 defer 的执行顺序

defer 的作用就是把关键字之后的函数执行压入一个栈中延迟执行，多个 defer 的执行顺序是后进先出 LIFO：

1
2
3

defer func() { fmt.Println("1") }()
defer func() { fmt.Println("2") }()
defer func() { fmt.Println("3") }()

输出顺序是 321。

这个特性可以对一个 array 实现逆序操作。

被 deferred 函数的参数在 defer 时确定

这是 defer 的特点，一个函数被 defer 时，它的参数在 defer 时进行计算确定，即使 defer 之后参数发生修改，对已经 defer 的函数没有影响。什么意思？看例子：

1
2
3
4
5
6

func a() {
	i := 0
	defer fmt.Println(i)
	i++
	return
}

a 执行输出的是 0 而不是 1，因为 defer 时，i 的值是 0，此时被 defer 的函数参数已经进行执行计算并确定了。

再看一个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

package main

import (
	"fmt"
)

func calc(index string, a, b int) int {
	ret := a + b
	fmt.Println(index, a, b, ret)
	return ret
}
func main() {
	a := 1
	b := 2
	defer calc("1", a, calc("10", a, b))
	a = 0
	return
}

执行代码输出:

1
2

10 1 2 3 
1 1 3 4

defer 函数的参数，第三个参数在 defer 时就已经计算完成并确定，第二个参数 a 也是如此，无论之后 a 变量是否修改都不影响。

被 defer 的函数可以读取和修改带名称的返回值

1
2
3
4
5
6
7
8
9
10
11
12

package main

import "fmt"

func main() {
	fmt.Println(c())
}

func c() (i int) {
	defer func() { i++ }()
	return 1
}

被 defer 的函数是在 return 之后执行的，可以修改带名称的返回值，上面的函数 c 返回的是 2。

定义

前缀树，又称字典树、单词查找树、\(Trie\)树(发音类似 try)。它是一棵 \(N\) 叉树。前缀树的每一个结点代表一个字符串的前缀。每一个结点会有多个子结点， 通往不同子结点的路径上有着不同的字符。子结点代表的字符串是由结点本身的原始字符串，以及通往该子结点上所有的字符组成的。

前缀树的一个重要的特性是，结点所有的后代都与该结点相关的字符串有着共同的前缀，这是前缀树名称的由来。

例如，以结点 "b" 为根的子树中的结点表示的字符串，都具有共同的前缀 "b"。反之亦然，具有公共前缀 "b" 的字符串，全部位于以 "b" 为根的子树中，并且具有不同前缀的字符串来自不同的分支。

前缀树有着广泛的应用，例如自动补全，拼写检查等等。

实现 \(Trie\) 树

208. 实现 Trie (前缀树)

\(Trie\)，是一棵有根树，其每个结点包含以下字段：

• 指向子结点的指针数组 \(children\)。对于本题而言，数组长度为 26，即小写字母的数量。此时 \(children[0]\) 对应小写字母 \(a\)，\(children[1]\) 对应小写字母 \(b\)，...，\(children[25]\) 对应小写字母 \(z\)。
• 布尔字段 \(isEnd\)，表示该结点是否为字符串的结尾。

插入字符串

我们从字典树的根开始，插入字符串。对于当前字符对应的子结点，有两种情况：

• 子结点存在。沿着指针移动到子结点，继续处理下一个字符。
• 子结点不存在。创建一个新的子结点，记录在 \(children\) 数组的对应位置上，然后沿着指针移动到子结点，继续搜索下一个字符。

重复以上步骤，直到处理字符串的最后一个字符，然后将当前结点标记为字符串的结尾。

查找前缀

我们从字典树的根开始，查找前缀。对于当前字符对应的子结点，有两种情况：

• 子结点存在。沿着指针移动到子结点，继续搜索下一个字符。
• 子结点不存在。说明字典树中不包含该前缀，返回空指针。

重复以上步骤，直到返回空指针或搜索完前缀的最后一个字符。

若搜索到了前缀的末尾，就说明字典树中存在该前缀。此外，若前缀末尾对应结点的 \(isEnd\) 为真，则说明字典树中存在该字符串。

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

public class Trie {
    private Trie[] children;
    private boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }

    public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }

    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }

    private Trie searchPrefix(String prefix) {
        Trie node = this;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                return null;
            }
            node = node.children[index];
        }
        return node;
    }

    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }
}

定义

线段树（segment tree），顾名思义，是用来存放给定区间（segment，or interval）内对应信息的一种数据结构。与树状数组（binary indexed tree）相似， 线段树也用来处理数组相应的区间查询（range query）和元素更新（update）操作。与树状数组不同的是，线段树不止可以适用于区间求和的查询，也可以进行区间最大值， 区间最小值（Range Minimum/Maximum Query problem）或者区间异或值的查询。

对应于树状数组，线段树进行更新（update）的操作为 \(O(log_n)\)，进行区间查询（range query）的操作也为 \(O(long_n)\)。

实现原理

从数据结构的角度来说，线段树是用一个完全二叉树来存储对应于每一个区间（segment）的数据。该二叉树的每一个结点中保存着对应于这一个区间的信息。 同时，线段树所使用的这个二叉树是用一个数组保存的，与堆（Heap）的实现方式相同。

例如，给定一个长度为 \(N\) 的数组 \(arr\)，其所对应的线段树 \(T\) 各个结点的含义如下：

1. \(T\) 的根节点代表整个数组所在的区间对应的信息，及 \(arr[0:N]\)（不含N）所对应的信息。
2. \(T\) 的每一个叶结点存储对应于输入数组的每一个单个元素构成的区间 \(arr[i]\) 所对应的信息，此处 \(0\leq i\lt N\)。
3. \(T\) 的每一个中间结点存储对应于输入数组某一区间 \(arr[i:j]\) 对应的信息，此处 \(0 \leq i \lt j \lt N\)。

以根结点为例，根结点代表 \(arr[0:N]\) 区间所对应的信息，接着根节点被分为两个子树，分别存储 \(arr[0:(N - 1)/2]\) 及 \(arr[(N - 1)/2:]\) 两个子区间对应的信息。也就是说，对于每一个结点，其左右子结点分别存储母结点区间拆分为两半之后各自区间的信息。也就是说对于长度为 \(N\) 的输入数组， 线段树的高度为 \(log_N\)。

对于一个线段树来说，其应该支持的两种操作为：

1. Update: 更新输入数组中的某一个元素并对线段树做相应的改变。
2. Query: 用来查询某一区间对应的信息（如最大值，最小值，区间和等）。

线段树的初始化

线段树的初始化是自底向上进行的。从每一个叶子结点开始（也就是原数组中的每一个元素），沿从叶子结点到根结点的路径向上按层构建。 在构建的每一步中，对应两个子结点的数据将被用来构建应当存储于它们母结点中的值。每一个中间结点代表它的左右两个子结点对应区间 融合过后的大区间所对应的值。这个融合信息的过程可能依所需要处理的问题不同而不同（例如对于保存区间最小值得线段树来说，merge 的过程应为 min 函数， 用以取得两个子区间中的最小区间最小值作为当前融合过后的区间最小值）。 但从叶子结点（长度为1的区间）到根结点（代表输入的整个区间）更新的这一过程是统一的。

注意此处我们对于 segmentTree 数组的索引从 1 开始算起。则对于数组中的任意结点 \(i\)，其左子结点为 \(2*i\)，右子结点为 \(2*i + 1\)，其母结点为 \(i/2\)。

构建线段树的算法描述如下：

1
2
3
4
5
6
7
8
9
10
11

construct(arr):
    // n 是子结点所在那一层的节点个数
    n = length(arr)
    // 开 2 * n 的数组，这样就可以一半用来存储子结点（叶子结点存储的是一个数组成的区间），一半用来存储非叶子结点（非叶子结点存储的是区间汇总信息）
    segmentTree = new int[2 * n]
    // 先初始化的是叶子结点，叶子结点的范围是 [n, 2 * n - 1]
    for i from n to 2 * n - 1:
        segmentTree[i] = arr[i - n]
    // 初始化父结点，就是合并区间的操作，通过左右叶子结点得到区间汇总信息
    for i from n - 1 to 1:
        segmentTree[i] = merge(segmentTree[2 * i], segmentTree[2 * i + 1])

这里有几个点要说明（对于上面的遍历范围）：

1. 完全二叉树每一层的结点个数为 \(2 ^ {n - 1}\)，（\(n\) 为自顶向下的层数，从 \(1\) 算起）
2. 假设完全二叉树的总节点数量为 \(2 * n\)，那么完全二叉树的叶子结点的下标范围为 \([n, 2 * n - 1]\)

例如给定一个输入数组 [1, 5, 3, 7, 3, 2, 5, 7]，其所对应的最小值线段树应如下图所示：

上面所示线段树每一个节点代表的区间则如下图所示：

上面所示线段树每一个结点代表的区间则如下图所示：

如果用其数组表示来说，则数组 segmentTree 中的每一个位置代表的区间如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

segmentTree[1] = arr[0:8)
segmentTree[2] = arr[0:4)
segmentTree[3] = arr[4:8)
segmentTree[4] = arr[0:2)
segmentTree[5] = arr[2:4)
segmentTree[6] = arr[4:6)
segmentTree[7] = arr[6:8)
segmentTree[8] = arr[0]
segmentTree[9] = arr[1]
segmentTree[10] = arr[2]
segmentTree[11] = arr[3]
segmentTree[12] = arr[4]
segmentTree[13] = arr[5]
segmentTree[14] = arr[6]
segmentTree[15] = arr[7]

更新

更新一个线段树的过程与上述构造线段树的过程相同。当输入数组中位于 \(i\) 位置的元素被更新时，我们只需要从这一元素对应的叶子结点开始， 沿二叉树的路径向上更新至根结点即可。显然，这一过程是一个 \(O(log_n)\) 的操作。其算法如下：

1
2
3
4
5
6
7
8
9
10

update(i, value):
    // 原数组在线段树里面的存储位置是从下标 n 开始的
    i = i + n;
    // 更新原数组的值
    segmentTree[i] = value;
    while (i > 1):
        // 向上更新关联的父结点，直到根结点。i / 2 是 i 的父结点在线段树中的下标。
        i = i / 2;
        // 如果父结点在线段树的下标为 i，那么左孩子在线段树的下标为 2 * i，右孩子在线段树的下标为 2 * i + 1
        segmentTree[i] = merge(segmentTree[2 * i], segmentTree[2 * i + 1])

例如对于上图中的线段树，如果我们调用 update(5, 6)，则其更新过程如下所示：

1. 修改原数组下标为 5 的元素为 6.

2. 修改原数组下标 5 在线段树里面的父结点，由 2 改为 3

3. 修改上一个修改结点的父结点，由 2 改为 3

4. 修改上一个修改结点的父结点，改为 1（跟原来一样）

区间查询

区间查询大体上可以分为 3 种情况讨论：

1. 当前结点所代表的区间完全位于给定需要被查询的区间之外，则不应该考虑当前结点。
2. 当前结点所代表的区间完全位于给定需要被查询的区间之内，则可以直接查看当前结点的母结点
3. 当前结点所代表的区间部分位于需要被查询的区间之内，部分位于其外，则我们优先考虑位于区间外的部分，后考虑区间内的 （注意总有可能找到完全位于区间内的结点，因为叶子结点的区间长度为 1，因此我们总能组合出合适的区间）

以求最小值为例，其算法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

minimum(left, right):
    // left 在线段树中的下标位置
    left = left + n
    // right 在线段树中的下标位置
    right = right + n
    // 初始化最小值
    minimum = Integer.MAX_VALUE
    while left < right:
        if left is odd:
            // left is out of range of parent interval, check value of left node first, then shift it right in the same level
            minimum = min(minimum, segmentTree[left])
            left = left + 1
        if right is odd:
            // right is out of range of current interval, shift it left in the same level and then check the value
            right = right - 1
            minimum = min(minimum, segmentTree[right])
        
        // 向根结点遍历
        left = left / 2
        right = right / 2

为什么是奇数的时候做处理呢？具体看下图：

假设要求 \([1, 7)\) 范围内的最小值：

我们来看看只有三个节点的情况：

1. 如果 \(left\) 是奇数，那就是上图里面 2 的位置，那么在这三个节点里面，唯一可能的值就是右下角的值 2。
2. 如果 \(right\) 是奇数，那就是上图里面 2 的位置，在这三个节点里面，因为我们取值范围不含右边界，那么在这三个节点里面，唯一可能的值就是左下角的值。

因此对于下标是奇数的情况，其父节点不需要考虑，只需要考虑当前结点。

\(n\) 不是 2 的次方怎么办？

注意上面的讨论中我们由于需要不断二分区间，给定的输入数组的长度 \(n\) 为 2 的次方。那么当 \(n\) 不是 2 的次方，或者说， 当 \(n\) 无法被完全二分为一些长度为 1 的区间时，该如何处理呢？

一个简单的方法就是在原数组的结尾补 0，直到其长度正好为 2 的次方位置。但事实上这个方法比较低效。 最坏情况下，我们需要 \(O(4n)\) 的空间来存储相应的线段树。例如，如果输入数组的长度刚好为 \(2^x + 1\)，则我们首先需要补 0 直到数组长度为 \(2^(x + 1) = 2 * 2^x\) 为止。 那么对于这个补 0 过后的数组，我们需要的线段树数组的长度为 \(2 * 2 * 2^x = 4 * 2 ^x = O(4n)\)。

其实上面所说的算法对于 \(n\) 不是 2 的次方的情况同样适用。这也是为什么我在上文中说线段树是一棵 完全二叉树 而非 满二叉树 的原因。

例如对于输入数组 \([4, 3, 9, 1, 6, 7]\)，其构造出的线段树应当如下图所示：

可以看出，在构造过程中我们事实上把一些长度为 1 的区间直接放在了树的倒数第二层来实现这个线段树。

Java 实现

Range Minimum 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

package com.baiguiren.leetcode;

import java.util.ArrayList;

public class MinSegmentTree {
    public static void main(String[] args) {
        MinSegmentTree tree = new MinSegmentTree(new int[]{1, 5, 3, 7, 3, 6, 5, 7});
        int min = tree.minimum(1, 2);
        System.out.println("min=" + min);
    }

    private ArrayList<Integer> minSegmentTree;
    private int n;

    public MinSegmentTree(int[] arr) {
        n = arr.length;
        minSegmentTree = new ArrayList<>(2 * n);

        for (int i = 0; i < n; i++) {
            minSegmentTree.add(0);
        }

        for (int i = n; i < 2 * n; i++) {
            minSegmentTree.add(arr[i - n]);
        }

        for (int i = n - 1; i > 0; i--) {
            minSegmentTree.set(i, Math.min(minSegmentTree.get(2 * i), minSegmentTree.get(2 * i + 1)));
        }
    }

    public void update(int i, int value) {
        i = i + n;
        minSegmentTree.set(i, value);

        while (i > 1) {
            i = i / 2;
            minSegmentTree.set(i, Math.min(minSegmentTree.get(2 * i), minSegmentTree.get(2 * i + 1)));
        }
    }

    public int minimum(int left, int right) {
        left = left + n;
        right = right + n;
        int min = Integer.MAX_VALUE;

        // 如果 left == right 说明，最小值已经产生，只可能是下一层的数
        // left == right 说明缩减到只有一个数字的区间了。
        while (left < right) {
            if ((left & 1) == 1) {
                min = Math.min(min, minSegmentTree.get(left));
                left = left + 1;
            }

            if ((right & 1) == 1) {
                right--;
                min = Math.min(min, minSegmentTree.get(right));
            }

            left >>= 1;
            right >>= 1;
        }

        return min;
    }
}

Range Sum 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

public class SumSegmentTree {
    public static void main(String[] args) {
        SumSegmentTree tree = new SumSegmentTree(new int[]{1, 5, 3, 7, 3, 6, 5, 7});
        int sum = tree.sum(1, 3);
        System.out.println("sum=" + sum);
    }

    private final ArrayList<Integer> sumSegmentTree;
    private final int n;

    public SumSegmentTree(int[] arr) {
        n = arr.length;
        sumSegmentTree = new ArrayList<>(2 * n);

        for (int i = 0; i < n; i++) {
            sumSegmentTree.add(0);
        }

        for (int i = n; i < 2 * n; i++) {
            sumSegmentTree.add(arr[i - n]);
        }

        for (int i = n - 1; i > 0; i--) {
            sumSegmentTree.set(i, sumSegmentTree.get(2 * i) + sumSegmentTree.get(2 * i + 1));
        }
    }

    public void update(int i, int value) {
        i = i + n;
        sumSegmentTree.set(i, value);

        while (i > 1) {
            i = i / 2;
            sumSegmentTree.set(i, sumSegmentTree.get(2 * i) +sumSegmentTree.get(2 * i + 1));
        }
    }

    public int sum(int left, int right) {
        left = left + n;
        right = right + n;
        int sum = 0;

        while (left < right) {
            if ((left & 1) == 1) {
                sum += sumSegmentTree.get(left);
                left = left + 1;
            }

            if ((right & 1) == 1) {
                right--;
                sum += sumSegmentTree.get(right);
            }

            left >>= 1;
            right >>= 1;
        }

        return sum;
    }
}

问题背景

如果给你一个包含 5000 万个元素的数组，然后会有频繁的区间修改操作，比如让第 1 个数到第 1000万 个数每个数都加上 1，而且这种操作是频繁的。

此时，很容易想到的办法就是从 1 遍历到 1000万，每个加上 1，但如果这种操作很频繁的话，效率就可能会非常低下。

差分数组原理

假设现在有一个数组，\(nums=\{0, 2, 5, 4, 9, 7, 10, 0\}\)

那么差分数组是什么呢？

其实差分数组本质上也是一个数组，我们暂且定义差分数组为 \(d\)，差分数组 \(f\) 的大小和原来 \(d\) 数组大小一样，而且 \(f[i] = d[i] - d[i - 1]\)，(\(i\neq0\))。

它的含义是什么呢？就是原来数组 \(i\) 位置上的元素和 \(i-1\) 位置上的元素作差，得到的值就是 \(d[i]\) 的值。

所以，上面数组对应的差分数组值如下图所示：

那么构造这个数组有什么意义呢？

现在我们有这么一个区间操作，即在区间 \([1,4]\) 上，所有的数值都加上 3.

由上面的表格可以知道，这个操作在差分数组上，只影响到了差分数组区间其实位置和结束位置。

我们只需要修改一下差分数组的起始和结束位置，就可以记录这次的区间修改操作了。这样就可以把修改区间的时间复杂度 \(O(n)\) 降为 \(O(1)\)。

现在，我们如何根据差分数组 \(f\) 来推测 \(d\) 中某一个位置的值呢？

只需要求差分数组的前缀和即可。

差分数组定义

对于已知有 \(n\) 个元素的离线数列 \(d\)，我们可以建立记录它每项与前一项差值的差分数组 \(f\)，显然有：

\[ f[i]=\left\{ \begin{aligned} &d[i], &(i = 0) \\ &d[i] - d[i - 1], &(1 \leq i \lt n) \end{aligned} \right. \]

差分数组简单性质

1. 计算数列各项的值：数组第 \(i\) 项的值是可以用差分数组的前 \(i\) 项的和计算的，即 前缀和。
2. 计算数列每一项的前缀和：第 \(i\) 项的前缀和即为数列 \(f[i]\) 前 \(i\) 项的和。对差分数列求两次前缀和？

差分数组用途

1. 快速处理区间加减操作：

假如现在对数列中区间 \([L, R]\) 上的数加上 \(x\)，我们通过性质 1 知道，第一个受影响的差分数组中的元素为 \(f[L]\)，即令 \(f[L]+=x\)，那么后面数列元素在计算过程中都会加上 \(x\)； 最后一个受影响的差分数组中的元素为 \(f[R]\)，所以令 \(f[R+1]-=x\)，即可保证不会影响到 \(R\) 以后数列元素的计算。这样我们不必对区间内每一个数进行处理，只需要处理两个差分后的数即可；

2. 询问区间和问题：

由性质 2 我们可以计算出数列各项的前缀和数组 \(sum\) 各项的值；那么显然，区间 \([L, R]\) 的和即为 \(ans = sum[R] - sum[L - 1]\)

差分数组应用

leetcode 1109. 航班预订统计

对于预定记录 \(booking = [l, r, inc]\)，我们需要让 \(d[l - 1]\) 增加 \(inc\)，\(d[r]\) 减少 \(inc\)。特别地，当 \(r\) 为 \(n\) 时，我们无需修改 \(d[r]\)， 因为这个位置溢出了下标范围。如果求前缀和时考虑该位置，那么该位置对应的前缀和值必定为 0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] nums = new int[n];
        for (int[] booking : bookings) {
            nums[booking[0] - 1] += booking[2];
            if (booking[1] < n) {
                nums[booking[1]] -= booking[2];
            }
        }
        for (int i = 1; i < n; i++) {
            nums[i] += nums[i - 1];
        }
        return nums;
    }
}

写本文目的：网上讲解01背包问题的文章有很多，但看着这些文章感觉少了点什么，后来想想，好像都在讲解问题本身，然后给出答案，然后我们看这些文章的时候，好像都懂了，但是我们好像还是不知道什么是动态规划。因此本文就是要讲一讲01背包里面包含的动态规划思想。

什么是01背包问题

背包问题描述：

给定 n 件物品，物品的重量为 weights[i]，物品的价值为 values[i]。现挑选物品放入背包中，假定背包能承受的最大重量为 W，问应该如何选择装入背包中的物品，使得装入背包中物品的总价值最大？

01背包问题算是动态规划里面的基础问题了，网上已经有很多讲解01背包问题的文章了，而且讲得也很好。比如：

动态规划：关于01背包问题，你该了解这些！ 动态规划：关于01背包问题，你该了解这些！（滚动数组） 图解 | 你管这破玩意叫动态规划

还有就是《算法图解》里面的 9.1 背包问题，虽然标题是背包问题，但讲解的依然是01背包，算法图解里面的讲解算是很形象了。

如果完全不了解01背包问题的可以看上面几篇文章，讲得都挺好的，这里没有必要再讲一遍了。

01背包为什么叫01背包

想象一下，我们现在有一个背包，然后对于摆在我们面前的 n 件物品，我们都有两个选择，选或者不选，没有其他的选择了。

我们就可以使用 01 来表示这两种状态，0 表示不选择，1 表示选择。假设我们有 3 件物品，那么 [0, 1, 0] 就表示我们只选择了第 2 件物品。

也就是说，最终下来所有可能的不同组合情况共有 2^n 种（n 位，每位有两种可能，0 或 1）。

如果通过遍历所有可能的组合来求解 01背包 问题，那么时间复杂度将会是指数级别的。

什么是动态规划（维基百科）

这里照搬一下维基百科关于动态规划的一些描述。

动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

动态规划在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间。

动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解（对有些问题这个要求并不能完全满足，故有时需要引入一定的近似）。简单地说，问题能够分解成子问题来解决。

动态规划的适用情况：

1. 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
2. 无后效性。即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
3. 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率，降低了时间复杂度。

递归算法

在讲解01背包跟动态规划的关系之前，很有必要先看看递归算法是如何执行的，了解了递归算法的执行过程之后，后面我们就能知道动态规划的优势了。

说到递归，我们很容易想到斐波那契数列，因为斐波那契数列很容易地通过递归算法实现，如下，就几行代码：

1
2
3
4
5
6

public int f(int n) {
    if (n == 0 || n == 1)
        return n;

    return f(n - 1) + f(n - 2);
}

但是虽然它的代码很简单，但是执行的过程并没有那么简单。

我们可以将递归的执行过程想象成一个树状的结构，递归的执行过程如下图，因为 f(0) 和 f(1) 是已知的，所以叶子结点到 f(0) 或者 f(1) 的时候就结束了。

简单来讲，就是在求解的过程中，由大到小，依次求解，求解完左边之后，再求解右边，又进行一次由大到小的求解。在到达边界的时候，依次返回。

然后我们可以很容易发现，其实在递归的过程中，f(2) 和 f(3) 都被重复计算了，而且，我们的递归层数越多，被重复计算的子问题就越多。

递归有个问题是，子问题会被多次重复求解，这样会导致有很多时间浪费在做一些重复计算上。

递归与动态规划

对于斐波那契数列，有没有方法可以做到 f(2) 和 f(3) 只求解一次呢？

有的，先求解子问题即可，从斐波那契数列的定义，我们可以知道 f(n) + f(n + 1) = f(n + 2)，那么，如果我们要求 f(5)，我们可以从 f(0) 求解到 f(5)：

1
2
3
4

f(2) = f(0) + f(1)，f(0) 和 f(1) 不需要求解，可以直接得出
f(3) = f(1) + f(2)，上一步我们已经求解了 f(2) 了，我们加上 f(1) 就得到 f(3) 了，这一步利用了上一步的计算结果
f(4) = f(2) + f(3)，上一步我们已经求解了 f(3) 了，而且我们的 f(2) 在第一步已经求解了，我们这里直接利用了前两次计算的结果
f(5) = f(3) + f(4)，同理，这里利用了前两次计算的结果

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13

public int f(int n) {
    if (n <= 1) return n;
      
    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++){
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

所以这里的关键是什么呢？

1. 先求解子问题，记录下子问题的答案。
2. 逐步求解更大的问题，这个更大的问题可以直接利用前面的计算结果。

这跟动态规划有什么关系？就从动态规划的适用情况说吧：

1. 最优子结构：我们从小到大求解 f(n) 的过程中，每一个 f(i) 可以看作最优子结构，当然这里实际上并没有优劣一说，我们每一个 f(i) 都是唯一的（对于 01背包 这种就有最优子结构的说法了）。
2. 无后效性：我们在求解 f(i) 的时候，并不关心 f(i - 1) 和 f(i - 2) 是怎么得到的，我们只需要知道前面求解的结果，并不关系其过程。
3. 子问题重叠：我们在递归求解 f(5) 的时候，发现 f(2) 和 f(3) 都被重复计算了，f(2) 和 f(3) 就是重叠子问题。

所以我们可以看到，动态规划的关键是，先求解子问题，得到子问题的解，然后逐步求解更大的问题，对于更大的问题，直接利用子问题的结果（子问题的结果都是最优结果），不需要再次计算。逐步求解，直到我们得到最终问题的答案。

01背包的决策过程

假设我们有一个容量为 4 的背包，有三件物品，物品0重量为 1、价值为 15，物品1重量为 3、价值为 20，物品2重量为 4、价值为 30。

然后使用 dp[i] 表示不同的背包容量下所能获得的最大价值。我们的背包容量为 4，所以只需要计算到 dp[4] 即可。

1. 对于第一件物品，dp[1]、dp[2]、dp[3]、dp[4] 都是 15，因为只有容量大于等于 1 的时候我们才能装得下这件物品，然后可以获得其价值。

2. 对于第二件物品，dp[1]、dp[2] 依然是 15，因为只有容量为 3 的背包才能放得下第二件物品。

1. 对于 dp[3]，容量为 3 的时候，有两种情况

• 不放入这件物品，那么所能获得的价值依然是 15。
• 放入这件物品。但是放入之后，就要占据背包全部容量了，之前的所有物品都放不下了，但是我们可以获得更大的价值 20。因此 dp[3] = 20

因此在背包容量为 3，有前两件物品选择的情况下，我们所能获得的最大价值是 20。

2. 对于 dp[4]，容量为 4 的时候，我们可以选择不放入这件物品，那么所能获得的价值依然是 15。

• 不放入这件物品，那么所能获得的价值依然是 15。
• 放入这件物品。放入之后，我们的背包还剩容量 1，在之前的物品中，容量 1 所能获得的最大价值是 15。

因此在背包容量为 4，有前两件物品选择的情况下，我们所能获得的最大价值是 20 + 15 = 35，20 是当前物品的价值，15 是剩余背包容量所能获得的最大价值。

3. 对于第三件物品的分析过程类似在对第二件物品做决策的过程，不再赘述。

我们在决策的过程中，需要根据之前物品选择之后，不同背包容量的所能获得的最大价值来进行决定是否选择当前物品。这样就能保证我们每次选择都是最优的结果。

01背包问题里面的动态规划

我们可以从动态规划适用情况来看01背包问题：

1. 最优子结构

在 0~i 件物品选择之后，不同背包容量下所能获得的最大价值就是一个最优子结构。我们并不需要知道前面的 0~i 件物品具体是怎样选择的，我们只需要知道选择的最优结果即可。

之所以需要计算不同容量，是因为如果我们当前剩余背包容量放不下当前物品的时候，就需要求解放入当前物品后，剩余的背包容量的最大价值，然后加上当前物品的价值，就是放入当前物品所能获得的最大价值。

2. 无后效性

对于 0~i 件物品具体怎么选择，我们在决定要不要放入当前物品的时候，并不关心，我们只需要知道有某一种方案可以使得获得当前最大价值就行了，同时我们后面不管怎么选择都影响不到之前选择得到的最优结果。

3. 重叠子问题

我们在选择一件物品的时候，假设要放入当前物品，那就需要知道剩余背包容量的在之前的物品选择中所能获得的最大价值。而之前的物品选择中，不同容量下所能获得的最大价值就是子问题。

01背包里面的重叠子问题

下面的讲解跟回溯相关，想详细了解回溯的朋友可以看看这一篇文章：回溯算法理论基础！

如果直接从动态规划的角度来思考01背包问题里面的重叠子问题可能会比较困难。

但是还有一种算法可以求解01背包问题的，那就是回溯（本质是递归），但是上面也说了，时间复杂度太高了，指数级别的。但是从回溯的角度来看，就很好理解01背包里面的重叠子问题。

现在，假设我们有一个容量为 W 的背包，有 3 件物品 A、B、C，需要从这 3 件物品里面选取不同的物品加入背包，使得加入背包的价值最大。我们使用一个长度为 3 的数组来记录每一种不同的组合，数组的每一个元素使用 0 代替没有选中的状态，使用 1 来代替选中的状态。

用回溯算法的处理过程如下，下图的每一个节点里面，我们都计算从 0~W 的容量下，当前的组合能获得的最大价值。

从上图看来，我们不管是否选择了 A，都要再针对 B 和 C 做出同样的组合判断，但是我们要知道，对于不同的背包容量，B 和 C 组合能得到的最大价值都是固定的，跟 A 并没有关系。

所以如果使用回溯算法，对于选不选 A，后面对于 B 和 C 的组合我们都做了重复的计算了。

上图上色的部分就是重复计算的部分，当然还有其他的重复计算，这些重复计算的地方就是01背包里面的重叠子问题了。

所以01背包里面的重叠子问题就是，i 个物品在不同背包容量下的最大价值。

动态规划是怎么处理重叠子问题的

我们再回忆一下上面提到的斐波那契数列的优化写法，我们是通过计算更小的斐波那契数列，逐步计算到我们需要的那个数 n，在这个计算过程中我们可以直接使用前面的计算结果。

因此，对于01背包问题，我们其实也可以先求解重叠的子问题，然后将这些子问题的解保存下来，在解决更大的问题的时候直接使用前面计算的结果。

具体来说，可以怎么做呢？

就是每次做判断的时候，我们都去计算将这个物品加入背包或者不加入背包的情况下，0~W 不同的背包容量下所能获得的最大价值。

然后我们在对下一个物品进行选择的时候，可以用背包容量减去当前物品重量，得到一个一个剩余的背包容量，我们看剩余背包容量在前面物品的选择中最大价值是多少，加上当前物品的价值，就是加入当前物品之后所能获得的最大价值。

我们需要注意的是，加入这件物品之后，得到的最大价值未必比不加入这件物品的价值更大，这个时候就需要对比一下两种情况，哪一种情况能获得的价值最大，就是当前选择过的物品不同组合下所能获得的最大价值了。

在01背包里面，我们可以直接利用 0~i-1 件物品的选择结果，来判断是否将第 i 件物品加入到背包。

总结

01背包里面的动态规划思想（假设我们已经选择了 0~i-1 件物品，W 是背包容量）：

1. 最优子结构：0~i-1 件物品在不同的背包容量下能获得的最大价值是一个最优子结构。
2. 无后效性：我们在决定放不放第 i 件物品的时候，前面的 0~i-1 件物品是如何组合得到那个最大价值完全没影响。
3. 重叠子问题：在 0~i-1 件物品的不同组合中，0~W 所能获得的最大价值。