Algorithms

本文最后更新于：2022年11月27日 中午

一些算法思路， 持续更新。。。

理解一个算法没有任何意义

多练多写才是王道（应试角度）

排序

快速排序

基于分治思想，最难的是划分

  1. 确定分界点
  2. 调整区间
  3. 递归处理左右两边

有边界问题建议模板

模板

1
2
3
4
5
6
7
8
9
10
11
12
void quick_sort(int q[], int l, int r) {
	if(l >= r) return; 
	int x = q[l], i = l - 1, j = r + 1;
	
	while(i < j) {
		do i++; while(q[i] < x);
		do j--; while(q[j] > x);
		if(i < j) swap(q[i], q[j]);
	}
	quick_sort(q, l, j);
	quick_sort(q, j + 1, r);
}

如果在递归函数中用i，注意x不可以取q[l]，否则容易发生死循环

最开始的边界，如果是在最左侧或者最右侧，然后极端情况下，i与j没有交换过，在边界处相遇，此时下一次递归时，有一个区间会无限递归。比如取x为q[l]，在最左侧，然后i与j都是0，递归时又选择了i，递归区间是[0, -1]和[0, n-1]，无限递归。如果取x为q[r]，在最右侧，i与j都是n-1，递归时选择了j，递归区间为[0, n-1]和[n, n-1]，还是有无限递归。而且即使是x取q[(r+l)/2]，也要注意向上向下取整的问题，不能取到某个边界。所以必须一左一右

归并排序

基本思想也是分治，最难的是归并

  1. 找分界点（中间）
  2. 递归
  3. 归并 —— 合二为一 O(n)

利用双指针算法，遇到相同的，可以把第一个数组的元素先放进去，因为归并一般是稳定的。快排也可以是稳定的，只要能保证所有元素都不同即可，那如何保证呢？可以把数组的下标也参与到排序中，构建一个二元组，即可保证不同。

时间复杂度：O(nlogn)

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void merge_sort(int q[], int l, int r) {
    if(l >= r) return;
    
    int mid = (l + r) >> 1;
    merge_sort(q, l, mid); // 闭区间
    merge_sort(q, mid + 1, r);
    
    int k = 0, i = l, j = mid + 1;
    while(i <= mid && j <= r) {
        if(q[i] <= q[j]) temp[k++] = q[i++];
        else temp[k++] = q[j++];
    }
    
    while(i <= mid) temp[k++] = q[i++];
    while(j <= r) temp[k++] = q[j++];
    
    // target数组 ：q[l...r]
    for (i = l, j = 0; i <= r; i++, j++) {
        q[i] = temp[j];
    }
}

二分

整数二分

本质：有单调性一定可以二分，但是二分的不一定都是单调性。二分的本质是边界。某个性质在左侧满足，右侧不满足，这种边界点就可以二分找到。

直接上边界，没有边界的只是特殊情况。

从左到右的最后一个：if(true) l=mid; else r=mid-1，此时mid需要加上1

从右到左最后一个：if(true) r=mid; else l=mid+1，mid不需要加1.

1
2
3
4
5
6
7
8
9
10
11
//将区间[l, r]划分成[l, mid]和[mid + 1, r]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。
int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = (r - l) / 2 + l;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return l;
}
1
2
3
4
5
6
7
8
9
10
11
12
//将区间[l, r]划分成[l, mid - 1]和[mid, r]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。在于对左值的处理，这里左值的处理是 left = mid。因为正常的left+mid>>1都是向下取整，如果不加上1，left=mid会死循环
int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        // int mid = (r - l + 1) / 2 + l;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    return l;
}

选择模板，看如何更新，根据更新结果去改mid，因为C++整除都是向下取整，所以如果更新了l，那么mid需要加1，如果更新的是r，mid就不变。为什么更新l要加1的例子：如果l=r-1，算出来mid等于l，如果又true了，那么l=mid，区间没变，死循环。

eg：数的二分，check时，不是单调或者大小，二是性质，先定性质，而不是大小关系（当然大小关系可以作为性质）。比如大于等于x或者小于x，再比如大于x和小于等于x，不同的性质就可二分。但同时也要注意，一个性质取反后并不一定正确，比如想找到小于等于x的最后一个数字，此时不可用大于x的第一个数字作为性质，会多一个。

浮点数二分

不需要处理边界，因此更加简单。当区间长度很小时，我们就可以认为找到了答案。区间长度往往比要求的精度再小两个数量级。

浮点数二分甚至可以直接循环100次。不再管精度，相当于把区间长度除以2的100次方。

高精度

大整数相加

模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> add(vector<int>& A, vector<int>& B) {
    vector<int> C;
    
    int t = 0;
    for(int i = 0; i < A.size() || i < B.size(); i++) {
        if(i < A.size()) t+=A[i];
        if(i < B.size()) t+=B[i];
        
        C.push_back(t % 10);
        t /= 10; // 进位
    }
    
    return C;
}

前缀和&差分

前缀和

一维

1
s[i] = a[1] + a[2] +...+a[i];

如何求S[i]：for循环

作用：快速求出原数组中一段数字的和，基本也是唯一的应用

1
S[r] - S[l-1] = Sum[l, r]

tips：S[0] = 0，好处：方便处理边界。不仅求区间和，也能求前缀和。

二维

求前缀和：二维矩阵。

s[i][j]如何计算：

1
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];

用前缀和，子矩阵内所有元素的和：

1
s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];

差分

前缀和逆运算

给定a数组，构造一个数组b，使得给定数组是该数组的前缀和。

差分主要应对的场景：对于给定A数组一段区间的元素，统一进行加或减的操作，将O(n)变为O(1)

【l，r】区间中加c，则令b[l] += c, b[r + 1] -= c，从而达到修改原数组的效果。等到用原数组的时候再O(n)改回原数组。

差分没有构造的过程，可以认为a和b初始都是0，每一个初始值都可以认为是在[x, x]这个长度为1的区间加上c。也就是只有一个操作。

一维模板

构造：

1
2
3
4
void insert(int l, int r, int c) {
    b[l] += c;
    b[r + 1] -= c;
}

改回：

（所有b依次加起来是对应位置的a）

a[i] = b[i] + a[i - 1];

二维模板

核心操作：以（x1, y1）为左上角，（x2，y2）为右下角的子矩阵的所有数同时加上C。

构造：

1
2
3
4
5
6
void insert(int x1, int y1, int x2, int y2, int c) {
    b[x1][y1] += c;
    b[x1][y2 + 1] -= c;
    b[x2][y1 + 1] -= c;
    b[x2 + 1][y2 + 1] += c;
}

改回：(b是相邻元素的差，因此用所有b加起来是a，而且要分开，使得b元素更新，不然下一次用的还是旧的)

a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + b[i][j];

双指针

一般两大类，一类单线双向奔赴（快速排序），一类双线单向（归并排序），还有单线单向（一般借助单调性）

所有双指针算法都是O(n) , 能够将n方优化到O(n)

模板：

1
2
3
4
5
for (int i = 0, j = 0; i < n; i++) {
    while(j < n && check(i, j)) j++;
    
    // other logic
}

一般都可以先从暴力开始，寻找是否有单调关系。单调性在于：当i向一个方向变化时，j是否只可能向一个方向变化，能够证明这点，基本就可以双指针。

位运算

常见操作：

  • 求第k位：n >> k & 1
  • 返回x的最后一位1，Lowbit(x) = x & (-x)
  • lowbit的常见用法：求1的个数

为什么用补码：

计算机里面没有减法，我们是用加法做减法。

一个数的负数，应该满足的是x + (-x) = 0，所以-x = 0 - x，在用0减去x的时候我们需要在最前面借一位1，变成1000.000减去x，也就等价于x取反后再加1。

离散化

有些数据本身很大， 自身无法作为数组的下标保存对应的属性。如果这时只是需要这堆数据的相对属性， 那么可以对其进行离散化处理。当数据只与它们之间的相对大小有关，而与具体是多少无关时，可以进行离散化。

难点：

  • 去重
  • 如何算出离散化后的值（二分）

Essentially, we map the original number to a value which is the index of the discretization array. And the mapping rule is based on the order of the number.

离散化的本质是将数字本身key映射为它在数组中的索引index。所以通过二分求索引（value -> index)是离散化的本质。二分时，求的是数字离散化后将会在哪里，也就是下标。比如一个数组是[1, 5, 100, 2000]，通过二分，左边界是0，右边界是大小，我们将数字映射成他在数组中的大小顺序，也就是1，2，3，4。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int discretize(int x)
{
    int l = 0, r = alls.size();

    while (l < r)
    {
        int mid = (r - l) / 2 + l;
        if (alls[mid] >= x)
            r = mid;
        else
            l = mid + 1;
    }
    return r + 1; // plus one because we want to map original data to [1...n]
}

数据结构

每种数据结构都有自己的特点，优点或缺点，而我们使用数据结构一般都是看中了它能快速地支持某种操作。

链表

结构体加指针效率较低，尤其是new节点，一般十万个节点，平时笔试一般不会动态链表的方式，直接上数组。

数组模拟单链表（应用的较多的是邻接表（n个链表），邻接表最多的用处又是存储图和树，这样是用单链表做的）

模拟双链表，用来优化某些问题。

单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入一个数a
void insert(int a)
{
    e[idx] = a, ne[idx] = head, head = idx ++ ;
}

// 将头结点删除，需要保证头结点存在
void remove()
{
    head = ne[head];
}

双链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// add x after k
void add(int k, int x)
{
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;
    r[k] = idx;
    idx++;
}

// remove the k-th number
void remove(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

邻接表：把每个点的临边保存下来，就是n个单链表，可以用来保存图和树

栈

数组模拟比STL的好处：快

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const int N;
int stack[N], top;

// add element
stack[++top] = x;

//remove element
top--;

// is empty
if(top > 0) not empty
else empty

// top
stack[top]

队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int N;
int queue[N], head, tail = -1;

// insert element
q[ ++ tail] = x;

// pop element
head++;

// is empty
if(head <= tail) return false
else return true;

// get head
queue[head];

单调栈

常见的只有一类题型

给定一个序列，找到每一个数的左边比他小的 离他最近的数（或者右边）

同样先尝试暴力，然后抽象

随着i向右移动，j向左移动，我们可以把i左边所有的数字放到一个栈里，然后遍历这个栈，（从栈顶开始）。

那么这个栈有什么性质？或者说栈中是否有一些元素，他们永远不可能被输出？——如果x与y都在栈中，x在前，y在后，且y更小，那么x后续便不会被输出，所以栈中没有逆序对（x<y 且 a[x] > a[y]），也就是单调的了

每个元素只有一次进栈与出栈，因此复杂度是2n

1
2
3
4
5
int tt = 0;
for(auto x : a) {
    while(tt && stk[tt] >= x) tt--;
    stk[++top] = x;
}

单调队列

滑动窗口里面的最大值和最小值

先暴力，发现找最大值最小值是O(k)的复杂度，然后我们看看能不能转变成O(1)的复杂度（通过单调性，把没用的元素删掉），挖掘要点，转变

取最值的话是端点，找一个值可以二分

窗口是用队列去维护的，看看哪些元素是没用的

找最大值：

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
const int N;
int a[N], q[N];

// 最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i++)
{
    // add a element to q
    // q[hh]是窗口起点下标，如果太小，说明头该出去了
    if(hh <= tt && q[hh] < i - k + 1) hh++;
    // 缩小其实是从后向前缩小
    while (hh <= tt && a[i] <= a[q[tt]]) tt--;
    
    q[++tt] = i; // 先加进去，因为i可能是最小值（唯一的）
    if(i >= k - 1) printf("%d ", a[q[hh]]);//minimum
	
    puts("");
}

// 最大值
hh = 0, tt = -1;
for(int i = 0; i < n; i++)
{
    if(hh <= tt && q[hh] < i - k + 1) hh++;
    
    while(hh <= tt && a[i] >= a[q[tt]]) tt--;
    
    q[++tt] = i;
    
    if(i >= k - 1) printf("%d", a[q[hh]]);
}

// 实际上是双端队列
  • 暴力算法怎么做
  • 如何优化

Trie树

快速存储字符串集合的数据结构

Trie树一般字符不多，要么全大写要么全小写

模板：

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
const int N;
int son[N][26]; // 存储树中每个节点的子节点
int cnt[N]; // 每个元素的出现次数（统计词频）
int idx; // 为每个元素赋一个编号

void insert(string str) {
    int p = 0; // 第几层
    for (auto ch : str) {
        int x = ch - 'a';
        if (son[p][x] == 0) son[p][x] = ++idx;
        p = son[p][x];
    }
    cnt[p]++;
}

int query(string str) {
    int p = 0;
    for (auto ch : str) {
        int x = ch - 'a';
        if (son[p][x] == 0) return 0;
        p = son[p][x];
    }
    return cnt[p];
}

并查集

思路精巧，代码比较短，很受面试官喜欢

用法

并查集用来：

  • 将两个集合合并
  • 询问两个元素是否在一个集合中

并查集能以近乎O(1)的复杂度中实现。

用树的形式维护集合，树根节点的编号就是集合的编号。每个节点存储他的父节点。p[x] 表示x的父节点。

使用操作

  • 判断树根：p[x] == x

  • 求x的集合编号：while(p[x] != x) x=p[x];

  • 求x与y 是否在一个集合中：分别求编号

  • 合并集合：把一个树根放到另一个树上即可

优化——路径压缩

求编号的优化（之前是与树的高度成正比，需要n的循环）

如何优化：一旦找到某条路径的根节点，我们就把这条路上所有的节点都指向根节点。这样每一个点，最多走n步，之后每次都是一步。

模板

1
2
3
4
5
6
7
8
9
10
11
int find(int x)
{
    if (p[x] != x) p[x] = find(x); // 这里既递归处理，同时也有路径优化
    return p[x];
}

// merge set a and set b
p[find(x)] = find(b);

// Query a and b
find(a) = = find(b);

加上当前集合有多少元素（附加操作）

1
2
3
4
5
// when merge
size[find(b)] += size[find(a)];
p[find(x)] = find(b);

//之后直接返回size[find(a)]即可找到当前集合元素的个数

加上距离根节点的距离信息

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int p[N], d[N];

int find(int x)
{
    if(p[x] != x) {
        int par = find(p[x]);
        d[x] += d[p[x]];
        p[x] = par;
    }
    return p[x];
}
// 初始化时d[i] = 0

// 合并时
p[find(a)] = find(b); // a加入b
d[find(a)] = distance; // 根据具体问题，初始化find(a) 偏移量

堆

堆是一个完全二叉树，使用数组存储

两个基本操作：down(x) —— 往下调整， up(x) —— 往上调整

背景：小根堆

如果把一个数字变大了，那么我们应该把数字向下移动——down操作

如果把一个数字变小了，那么我们应该把数字向上走——up操作

注意堆的下标从1开始，因为如果从0开始，但是0的左儿子还是0，冲突

应用

  • 插入一个数 : heap[++ size] = x; up(x);
  • 求最小值 : heap[1];
  • 删除最小值 : heap[1] = heap[size]; size--; down(1);
  • 删除k处 : heap[k] = heap[size]; size--; down(k); up(k);
  • 修改任何一个元素 : heap[k] = x; down(k); up(k);可能变大变小，于是我们就都做一遍，注意这两个函数实际只会执行一个。
  • （后两个STL中没有）

建立堆：一个一个插是nlogn，我们可以实现n。

1
2
for (int i = size / 2; i ; i--) down(i);
// 最下一层不用down

实现

down

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int h[N];
int size;

void down(int u)
{
    int t = u; // u is original 
    if(u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
    if(u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if(u != t)
    {
        swap(h[u], h[t]);
        down(t); // 大的换到了t，继续down(t)
    }
}

up

1
2
3
4
5
6
7
8
9
void up(int u)
{
    while(u / 2 && h[u] < h[u / 2])
    {
        swap(h[u], h[u / 2]);
        u /= 2;
    }
}
// 更简单，因为up只有一个父节点

idx

不管是链表，Trie树还是堆，他们的基本单元都是一个个结点连接构成的，可以成为“链”式结构。这个结点包含两个基本的属性：本身的值和指向下一个结点的指针。按道理，应该按照结构体的方式来实现这些数据结构的，但是用数组模拟，主要是因为比较快。

原来这两个属性都是以结构体的方式联系在一起的，现在如果用数组模拟，如何才能把这两个属性联系起来呢，如何区分各个结点呢？

idx的操作总是++idx，这就保证了不同的idx值对应不同的结点，这样就可以利用idx把结构体内两个属性联系在一起了。因此，idx可以理解为结点。

对于单链表，利用idx联系结构体本身的值和next指针，因此e[idx]可以作为结点的值，ne[idx]可以作为next指针。同理可以理解双链表。

Trie树中有个二维数组 son[N] [26]，表示当前结点的儿子，如果没有的话，可以等于++idx。Trie树本质上是一颗多叉树，对于字母而言最多有26个子结点。所以这个数组包含了两条信息。比如：son[1] [0]=2表示1结点的一个值为a的子结点为结点2;如果son[1] [0] = 0，则意味着没有值为a子结点。这里的son[N] [26]相当于链表中的ne[N]。

堆中的每次插入都是在堆尾，但是堆中经常有up和down操作。所以结点与结点的关系并不是用一个ne[idx] [2]可以很好地维护的。但是好在堆是个完全二叉树。子父节点的关系可以通过下标来联系（左儿子2n，右儿子2n+1）。就数组模拟来说，知道数组的下标就知道结点在堆中的位置。所以核心就在于即使有down和up操作也能维护堆数组的下标（k）和结点（idx）的映射关系。

hash

场景

map，将一个大的集合空间，映射到从0到n的一个较小区间内。

实现快速添加与查找某个数

但可能会出现冲突，根据处理冲突的不同，分为两种：开放寻址与拉链法

存储结构

开放寻址法

不断找下一个可以允许的地方，找到目标地址后，不断向后看

只开一个一维数组，但要原数组的两到三倍，一般能够把冲突降低到比较小

1
2
3
4
5
6
7
8
9
int find(x) // 如果找到x，返回下标，如果没有，返回应该存储的位置
{
    int k = (x % N + N) % N;
    while(h[k] != null && h[k] != x) {
        k++;
        if(k == N) k = 0;
    }
    return k;
}

注：

设置一个常量用来代表“无穷大”。

比如对于int类型的数，采用INT_MAX，即0x7fffffff作为无穷大。但是以INT_MAX为无穷大，加一个正数会溢出。

所以常采用0x3f3f3f3f来作为无穷大。0x3f3f3f3f主要有如下好处：

  • 0x3f3f3f3f的十进制为1061109567，和INT_MAX一个数量级，即10^9数量级，而一般场合下的数据都是小于10^9的。
  • 0x3f3f3f3f * 2 = 2122219134，无穷大相加依然不会溢出。
  • 可以使用memset(array, 0x3f, sizeof(array))来为数组设初值为0x3f3f3f3f，因为这个数的每个字节都是0x3f。

拉链法

第一次映射后得到的其实是链表，每个槽是一个链（单链表），期望链的长度是1

其实也就是邻接表，在存储图的时候也是用这个方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int h[N], e[N], ne[N], idx = 0;
void insert(int x)
{
    int k = (x % N + N) % N; // N一般是一个质数，大于最大范围的质数
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx++;
}

bool query(int x)
{
    int k = (x % N + N) % N;
    for(int i = h[k]; i != -1; i = ne[i]) {
        if(e[i] == x) return true;
    }
    return false;
}

字符串哈希

将字符串看作p进制数，转换成数字，但是数字可能比较大，再去取模

  • 不能映射成0（A和AA一样）
  • p=131或者13331，Q等于2的64次方，可以假定没有冲突。2的64次方，刚好是无符号long long的大小，所以我们会发现不用取模，直接计算。每次溢出的时候，就等价于模2的64次方
  • 前缀哈希，可以获得子串哈希值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef unsigned long long ULL;
const int N;
ULL h[N], p[N];

// !!! notice p[0] = 1
p[0] = 1;
for(int i = 1; i <= n; i++) {
    p[i] = p[i - 1] * P; // 位权
}

ULL hash(string str) {
    for(int i = 1; i <= n; i++) {
        h[i] = h[i - 1] * P + str[i];
    }
}

// str1 == str2
bool equal(int l1, int r1, int l2, int r2) {
    return h[r1] - h[l1] * p[r1 - l1 + 1] == h[r2] - h[l2] * p[r2 - l2 + 1];
}

STL

公共的：size，empty，clear（队列无）

系统分配空间时，所需的时间与空间大小无关，与申请次数有关。因此vector采用倍增。不够的时候，再申请两倍，然后把之前的copy过来。如果申请n个元素，第一次copy1个，然后2个，4个，8个，最后到了n/2个，申请次数是logn，但copy次数均摊下来每个元素都近似O(1)

vector

front, back, push_back, pop_back

支持比较运算

pair

二元组，两种属性，且需要排序

相当于两个变量的结构体加上一个比较函数

string

  • substr：begin and length
  • c_str: char array

queue

push pop back front

priority_queue

push top pop

用堆实现，默认大根堆。如何小根堆

  • 插入时插入-x，取出时再变成原来的数字
  • 定义时：priority_queue<int, vector<int>, greater<int>>

stack

push pop top

deque

front back push_back pop_back push_front pop_front []

set/multiset

insert find count erase

  • erase : 参数为x：删除所有x；参数为迭代器，删一个
  • lower_bound：返回大于等于x的最小的数
  • upper_bound：返回大于x的最小的数

map

根据索引取值—— [ ] – 时间复杂度是logn

无序家族

基本都是O1，但不支持lower_bound，upper_bound（因为无序），++，–

DFS & BFS

DFS空间需要O(h) , 与树高度成正比。BFS空间则是2的h次方，但是BFS有最短路的概念，能够用于找最短的东西。

DFS

每个DFS都一定对应一个搜索树

关键是想清楚顺序，两个要点：回溯（恢复现场）和剪枝

全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void dfs(int u)
{
    if(u == n) {
        for() // output
    }
    
    for(int i = 1; i <= n; i++) { // 树横向扩
        if(!st[i]) { // unused
            path[u] = i;
            st[i] = true;
            dfs(u + 1);
            st[i] = false;
        }
    }
}

八皇后

多种思路

如果分析出每一行只可能会有一个皇后，那么唯一的变数就是皇后在每一行的位置了（也就是列），所以可以使用全排列的思路做，大小为n的全排列（以行为单位枚举）

时间复杂度为n乘以n的阶乘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void dfs(int u)
{
    if(u == n) {
        for(int i = 0; i < n; i++) {
            printf("%s", chess[i]);
            puts("");
        }
        puts("");
    }
    
    for(int i = 0; i < n; i++) { // i is col
        // [u, i]这个点在哪条对角线上面
        if(!col[i] && !dg[u + i] && !udg[n + u - i]) {
            chess[u][i] = 'Q';
            col[i] = dg[u + i] = udg[n + u - i] = true;
            dfs(u + 1);
            col[i] = dg[u + i] = udg[n + u - i] = false;
            chess[u][i] = '.';
        }
    }
}

但也可以格子为单位去枚举，每一个格子都有放和不放两种可能

时间复杂度为2的n方次方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void dfs(int x, int y, int s)
{
    if(y == n) y = 0, x++; // next line
    // 代替了二重循环的格式
    
    if(x == n) {
        if(s == n) {
            // print
        }
    }
    
    dfs(x, y + 1, s); // 不放
    
    // 放
    if(!row[x] && !col[y] && !dg[x + y] && !udg[n + x - y]) {
        chess[x][y] = 'Q';
        row[x] = col[y] = dg[x + y] = udg[n + x - y] = true;
        dfs(x, y + 1, s + 1);
        row[x] = col[y] = dg[x + y] = udg[n + x - y] = false;
        chess[x][y] = '.';
    }    
}

BFS

dp问题和最短路问题其实是互通的，dp是一种特殊的最短路问题（无环存在的最短路问题）

边权为1 时，BFS才能做最短路

1
2
3
4
5
6
7
8
9
10
11
12
13
void bfs()
{
    queue q;
    q.push(init);
    
    while(!q.empty())
    {
        auto h = q.front();
        q.pop();
        // extense other data
        q.push(xxxxx);
    }
}

Tree & Graph

树是一种特殊的图，无环连通图

图：有向图和无向图（无向图是特殊的有向图）

邻接矩阵储存（不常用）

邻接表

每个节点都是单链表

tip：输入超过1M的时候cin和scanf才有区别

树和图的深度优先遍历和宽度优先遍历，是一种特殊的深度优先搜索和宽度优先搜索。

深度优先搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int N = 10e5;
int h[N], e[N * 2], ne[N * 2];
bool st[N]; // flag

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u)
{
    st[u] = true; // been searched
    for(int i = h[u]; i != - 1; i = ne[i]) { // u的所有出边
        int j = e[i];
        if(!st[j]) dfs(j);
    }
}

广度优先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 求最短路（需要权重为1）
int bfs()
{
    memset(d, -1, sizeof d);
    d[1] = 0;
    
    queue<int> q;
    q.push(1);
    
    while(q.size())
    {
        int t = q.front();
        q.pop();
        
        for(int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if(d[j] == -1) {
                d[j] = d[t] + 1;
                q.push(j);
            }
        }
    }
    return d[n];
}

图宽搜的应用 - 拓扑排序

求有向图的拓扑排序

拓扑序列所有边都是从前指向后面的。因此有环图不可能有拓扑序列。

有向无环图 = 拓扑图

入度、出度。

因此所有入度为0的点都可以作为起点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
d[N]; // ru du
bool topo_sort()
{
    int hh = 0, tt =-1;
    for(int i = 1; i <= n; i++) {
        if(d[i] == 0) q[++tt] = i;
    }
    
    while(hh <= tt) {
        int t = q[hh++];
        for(int i = h[t]; i != -1; i++) {
            int j = e[i];
            if(--d[j] == 0) {
                q[++tt] = j;
            }
        }
    }
    return tt == n - 1; // tt start from 0, when tt is n - 1, all points have entered the queue
}

最短路

不证明算法的正确性，考察问题抽象，使得原问题变成一个最短路问题，抽象边与顶点

图论侧重于实现，不在于原理

单源最短路

源：起点，汇：终点

n: 顶点数量，m：边数量

稠密图：m是n^2级别

稀疏图：m与n是一个级别

无负权

朴素Dijkstra算法

O(n^2), 与边无关，适应于稠密图（存储用邻接矩阵），边多

伪代码：

1
2
3
4
5
6
1. dist[src] = 0, dist[other] = +infinite
	s：当前已经确定最短距离的点的集合
2. for v : i —> n
		t =  不在s中的距离最近的点
    	把t加入到s中
        用t更新其他点的距离

基于贪心思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0; // node start from 1
    
    for(int i = 0; i < n; i++ ){
        int min_dist = -1;
        for(int j = 1; j <= n; j++) {
            if(!st[j] && (min_dist == -1 || dist[min_dist] > dist[j])) {
                min_dist = j;
            }
        }
        
        st[min_dist] = true;
        
        for(int j = 1; j <= n; j ++) {
            dist[j] = min(dist[j], dist[min_dist] + g[min_dist][j]);
        }
    }
    
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

堆优化的Dijkstra算法

O(mlogn) ，适应于稀疏图（存储用邻接表），如果边多，变成O(n^2logn)

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
int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0, 1});
    dist[1]= 0;
    
    while(q.size())
    {
        auto t = q.top();
        q.pop();
        	
        int distance = t.dirst, num = t.second;
        
        if(st[num]) continue;
        st[num] = true;
        
        for(int i = h[num]; i != -1; i = ne[i]) {
            int j = e[i]; // j是节点编号，i是一个节点（idx）
            if(dist[j] > dist[num] + w[i]) {
                dist[j] = dist[num] + w[i];
                q.push({dist[j], j});
            }
        }
    }
    
    if(dist[n] == 0x3f3f3f3f) return -1;
    return dist[n];
}

有负权

Bellman-Ford

贝尔曼-福特算法与迪科斯彻算法类似，都以松弛操作为基础，即估计的最短路径值渐渐地被更加准确的值替代，直至得到最优解。在两个算法中，计算时每个边之间的估计距离值都比真实值大，并且被新找到路径的最小长度替代。 然而，迪科斯彻算法以贪心法选取未被处理的具有最小权值的节点，然后对其的出边进行松弛操作；而贝尔曼-福特算法简单地对所有边进行松弛操作，共 |V| - 1次，其中 V 是图的点的数量。在重复地计算中，已计算得到正确的距离的边的数量不断增加，直到所有边都计算得到了正确的路径。这样的策略使得贝尔曼-福特算法比迪科斯彻算法适用于更多种类的输入。

循环

每次循环操作实际上是对相邻节点的访问，第 k 次循环操作保证了所有深度为 k 的路径最短。由于图的最短路径最长不会经过超过 V - 1条边，所以可知贝尔曼-福特算法所得为最短路径。

迪科斯彻算法的基本操作“拓展”是在深度上寻路，而“松弛”操作则是在广度上寻路，这就确定了贝尔曼-福特算法可以对负边进行操作而不会影响结果。

O(nm)，可以用来求不超过k条边的最短路

1
2
3
4
5
for 1 : n // 经过k次，k的意义：经过不超过k条边，走到每个点的最短距离
    for edge a, b, w
        dist[b] = min(dist[b], w); // 松弛操作

// 经过循环，dist[b] <= dist[a] + w （三角公式）

n次迭代，每一次循环所有边，a, b, w

如果迭代n次，第n次还有更新，说明经过n条边，n条边意味着n+1个顶点，所以有环，但是由于条件是选更小的路径，说明有负环。（可以求负环，但不怎么用）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int dist[N], backup[N];
struct Edge {
    int a, b, w;
} edges[N];
int bellman() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for(int i = 0; i < k; i++) { 
        memcpy(backup, dist, sizeof dist);
        // k is the limit of edge number
        for(int j = 1; j <= m; j++) { // 
            int a = edges[j].a, b = edges[i].b, w = edges[i].w;
            dist[b] = min(dist[b], backup[a] + w);
        }
    }
}

SPFA

SPFA：对上面优化，一般是O(m)，最坏O(nm)

思路：一个边要想更新，那么这条路径上他前面的边必须先更新。换句话说，只有更新过的边才有资格去更新别人。因此可以用一个队列去保存更新过的边。

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
int h[N], e[N], ne[N], w[N];
int st[N], dist[N];
void add(int a, int b) { e[idx] = b, ne[b] = h[a], h[a]=idx++;}

int spfa() {
    memset(dist, 0x3f, sizeof dist);
    queue<int> q;
    
    dist[1] = 0;
    q.push(1);
    
    while(q.size())
    {
        auto t = q.front(), q.pop();
        st[t] = false;
        for(int i = h[t]; i != -1; i = ne[i]) {
            int j = e[i];
            if(dist[j] > dist[i] + w[i]) {
                dist[j] = min(dist[j], dist[t] + w[i]);
                if(!st[j]) {
                	st[j] = true;
                	q.push(j);
            	}
            }
            
        }
    }
    if(dist[n] > 0x3f3f3f3f / 2) return -100;
    else return dist[n];
}

spfa判断负环

在寻找最短路过程中，记录一个cnt数组，只要在寻找过程中出现了大于等于n的路径，那么说明有n+1个点，说明有环，找的是最短的，所以是负环。

注意：此时初始化时不能只放起点，因为可能有负环但是某个点到不了，所以需要把所有的点放进去

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
bool spfa()
{
	queue<int> q;
	for(int i = 1; i <= n; i++) {
		st[i] = true;
		q.push(i);
	}

	while(q.size())
	{
		auto t = q.front();
		q.pop();

		st[k] = false;
		for(int i = h[t]; i != -1; i = ne[i]) {
			int j = e[i];
			if(dist[j] > dist[t] + w[i]) {
				dist[j] = dist[t] + w[i]; 
                // 利用的是最短路去找负环，这样才能在找到n条边的时候断定有负环
				cnt[j] = cnt[t] + 1;
				if(cnt[j] >= n) return true;
				if(!st[j]) {
					st[j] = true;
					q.push(j);
				}
			}
		}
	}

	return false;
}

多源汇最短路

任意两个点的最短路

Floyd算法——O(n^3) （动态规划）

1
2
3
4
5
6
7
8
for(int k = 1; k <= n; k++) {
    for(int i = 1; i <= n; i++) {
        for(int j =1; j <= n; j++) {
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }
    }
}

d[k,i,j] : 从i点开始，经过1到k的中间点，到达j的最短距离

k是阶段，先枚举k，从k-1转移过来

1
dist[k, i, j] = dist[k - 1, i, k] + dist[k - 1, k, j]

从i到j经过1到k = 1到k-1的阶段，加上第k个点，就是从i到k，再从k到j

最小生成树

Prim

  • 初始化距离最大值
  • n次循环，每次找到集合外的到集合最近的点t，用t更新其他点到集合的距离
  • prim中的dist[t]，代表的是t这个点到集合的最短距离
  • 对于重边，保留最小值，对于自环，不用管，因为最小生成树里面没有环，实际上只要我们把一个有自环的点放入进去，后续就不会再管到自环
  • 与Dijkstra算法很像，不同点在于dist[t]的意义，D代表的是t这个点到起点的最短距离，P中代表的是到集合的最短距离
  • 先累加再更新，否则自环对于权值计算有影响，一个有自环的点，是经过其他的边进入的集合，和负权自环无影响，但是如果更新了，那么这个点到集合的最短距离可能变成了自环上的负数，有影响。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int prim()
{
    memset(dist, 0x3f, sizeof dist);
    int res = 0;
    for(int i = 0; i < n; i ++) {
		int t = -1;
        for(int j = 1; j <= n; j ++) {
            if(!st[j] && (t == -1 || dist[j] < dist[t])) {
                t = j;
            }
        }
        
        if(i && dist[t] == INF) return INF;
        
        st[t] = true;
        if(i) res += dist[t];
        // 第一个点到集合距离应该为0
        for(int j = 1; j <= n; j++) {
            dist[j] = min(dist[j], g[t][j]);
        }
    }
    return res;
}

Kruskal

  • 将所有边按照权重从小到大排序 O(mlogm)，快排，但是快排常数小
  • 枚举每条边，如果两个点不在一个集合，加入到一个集合，更新res
  • 由于该算法只关注边，不关注顶点，所以直接结构体存储即可，不需要邻接

二分图

染色法

  • 判断一个图是不是二分图
  • 一个图是二分图当且仅当图中不含有奇数环

匈牙利

数学知识

质数

质数判定——试除法

b | a表示b整除a，即a是b的倍数

循环除法找到，但是O(n)，同时利用约数的性质，约数都是一对一对出现的，如果b | a, 那么 a/b | a，所以不需要枚举到a - 1，只需要枚举到a/b即可，变成logn

1
2
3
4
5
6
7
bool is_prime(int n) {
    if (n <= 1) return false;
    for(int i = 2; i <= n / i; i++ ) {
        if(n % i == 0) return false;
    }
    return true;
}

分解质因数——试除法

  • 从小到大枚举所有因数(brust)——枚举所有数也可以，不需要仅枚举质数。因为当我们枚举到i的时候，n中已经不包含任何2到n-1的质因子了
  • n中最多只包含一个大于根号n的质因子，因为如果有两个的话，相乘大于n，否定。因此只需要先枚举到根号n的地方，剩下的如果大于1，就是大于根号n的质因子，最后一个
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void divide(int n)
{
    for(int i = 2; i <= n / i; i ++){
        if(n % i == 0) { // i must be 质数
            int cnt = 0;
            while(n % i == 0) {
                n /= i;
                cnt++;
            }
            cout << i << " " << cnt << endl;;
        }
    }
    if(n > 1) cout << n << endl;
}

筛选质数

如果循环再依次判断，复杂度较高

每当遍历到一个，直接将他所有的倍数去除，也就是for循环每次加自己即可

优化后能够达到O(n)，只把质数的倍数去掉即可

1
2
3
4
5
6
7
8
for(int i = 2; i <= n; i ++ ) {
        if(!st[i]) {
            primes[cnt ++ ] = i;
            for(int j = i + i; j <= n; j += i) {
                st[j] = true; // 遍历过，且必为合数
            }
        }
    }

约数

求约数

  • 试除法，成对出现，与质数类似
1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> get_divisors(int n)
{
    vector<int> res;
    for(int i = 1; i <= n; i ++ ) {
        if(n % i == 0)
        {
            res.push_back(i);
            if(i != n / i) {
                res.push_back(n / i);
            }
        }
    }
    sort(res.begin(), res.end());
}

约数个数

基于约数个数定理

image-20221106202640167

知道质因数组成，则对a进行组合即可，每种组合对应一个约数

  • int范围内最多也就是1500多个约数

  • 12 ：1，2，3，4，6，12

  • 12 = 2 * 2 * 3

动态规划

模型（如背包）、线性DP，区间DP，状态压缩DP

背包

  • 01背包（一个物品用一次）
  • 完全背包（没有限制）
  • 多重背包（每种物品数量不一样，告诉有几个）
  • 分组背包（n组，每一组里有若干种，每一组选一个）

01背包

状态表示

f[i][j]，考虑需要几维来表示状态，每一个状态的含义是什么

  • 状态的集合是什么
    • 所有选法
    • 只从前i个物品里面选
    • 总体积 <= j
    • 满足上面两个条件的所有选法的集合
  • f[i][j]的数值就是状态的属性是什么（最大值，最小值，数量）

状态计算：

把每一个状态计算出来

  • 对应集合的划分
  • 分成更小的子集，使得子集都能计算出来
  • 背包中，分为两大类：含i和不含i
  • 划分原则：不重复、不漏掉
  • 不含i的最大值：从1到i中选，总体积小于j，并且不包含i。合并这三个条件，就是从1到i-1，总体积小于j，选择的最大值，也就是f[i][j - 1]。注意一定存在
  • 含i的最大值：从1到i中选，总体积小于j，并且我必须要包含第i个元素。直接求不好求，可以先把i去掉，同时体积也减去vi，因为这种条件下，反正都是要选择第i个物品的，那么我们把第i个物品的价值和体积先拿出来，最大的价值还是最大的，最后再加上第i个物品的价值。此时最大的情况是i-1 和 j - vi，再统一加上第i个物品的价值，也就是f[i-1][j-vi] + wi。注意不一定存在，如果当前物品体积大于背包目前最大容量的时候，那么就不存在了。
  • 但是要注意，含i的情况，可能不存在，就是指现在背包的容量已经装不下第i个物品了

优化：一般都是对dp方程作等价变形，先做朴素的

状态的集合，i和j就变成了元素的属性

dp问题是没有模板的，具体问题具体分析。

伪代码

1
2
3
4
5
6
7
8
for(int i = 1; i <= n; i++) {
  for(int j = 0; j <= V; j ++ ) {
    dp[i][j] = dp[i - 1][j];
    if(j >= v[i]) {
      dp[i][j] = max(dp[i][j], w[i] + dp[i - 1][j - v[i]]); 
    }
  }
}

一维优化

1
2
3
4
5
for(int i = 1; i <= n; i++) {
  for(int j = V; j >= v[i]; j--) {
    dp[j] = max(dp[j], w[i] + dp[j - v[i]]);
  }
}

完全背包

状态表示与上面一样

状态计算

划分集合，将总的划分成 第i个物品选择0-k个，这些情况

image-20221120151615069

对于每一种情况，再去分别考虑：

  • 第i个物品选了0个，对应01背包里面不选择的情况f[i][j] = f[i - 1][j]
  • 第i个物品选了1个，对应01背包里面选择的情况：f[i][j] = w[i] + f[i - 1][j - w[i]]
  • 第i个物品选了2个，仍然采取曲线的方式，先把这俩放进去，再考虑后面的最大值：f[i][j] = w[i] * 2 + f[i - 1][j - v[i] * 2]
  • 第i个物品选了k个：f[i][j] = k * w[i] + f[i - 1][j - k * v[i]]

伪代码

1
2
3
4
5
6
7
for(int i = 1; i <= n; i ++ ) {
  for(int j = 0; j <= V; j ++ ) {
    for(int k = 0; k * v[i] <= j; k ++ ) {
      dp[i][j] = max(dp[i][j], w[i] * k + dp[i - 1][j - k * v[i]]);
    }
  }
}

可能超时

优化版

我们发现：

f[i][j] = max(f[i-1][j], f[i-1][j-v]+w, f[i-1][j-2v]+2w, f[i-1][j-3v]+3w)....

f[i][j-v] = max(f[i-1][j-v], f[i-1][j-2v]+w, f[i-1][j-3v]+2w), f[i-1][j-4v]+3w....)

由上式可得：

f[i][j] = max(f[i - 1][j], f[i][j-v] + w)

又变成了两种情况：不拿第i个，变成了f[i-1][j]，如果拿第i个的话，由于是无限个，所以其实还是考虑前i个物品，只不过此时体积变了。整体变成了f[i][j-v]+w

1
2
3
4
5
for(int i = 1; i <= n; i ++ ) {
  for(int j = v[i]; j <= V; j ++ ) {
    dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i]);
  }
}

注意：上面的伪代码有个问题，如果不拿的话，肯定还是能更新f[i][j]的，但是如果把j初始设置为最小体积，会导致不拿时候更新出错，也就是不再更新。还是尽量分开讨论，先把能更新的更新掉，之后再看体积问题。

1
2
3
4
5
6
7
8
for(int i = 1; i <= n; i ++ ) {
  for(int j = 0; j <= V; j ++ ) {
    dp[i][j] = dp[i - 1][j]; // 必定可以更新
    if(j >= v[i]) {
      dp[i][j] = max(dp[i][j], dp[i][j - v[i]] + w[i]); // 根据情况更新
    }
  }
}

一维优化

将二维变成一维

1
2
3
4
5
6
7
8
9
10
for(int i = 1; i <= n; i ++ ) {
  for(int j = 0;j <= V; j ++ ) {
    dp[j] = dp[j]; // delete
    // 因为把上面这一句删掉，所以下面的if语句没有用了，所以才可以在for循环的初始化时候设置v[i]
    if(j >= v[i]) { // 由于循环内只有这个判断，因此才可以修改j的初始值
      dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
      // 循环不需要倒置过来，之前01背包之所以倒置，是因为我们本来想用第i-1层的更新第i层的，但是不倒置的话，就是用第i层更新第i层，而这刚好符合我们完全背包的需求，所以不需要逆向循环
    }
  }
}

tips

总结：

  • 01背包：用第i-1层更新第i层
  • 完全背包：用第i层更新第i层

多重背包

状态表示与01背包相同

状态计算

与完全背包其实类似，只不过完全背包的k，变成了每种物品的数量

1
2
3
4
5
6
7
for(int i = 1; i <= n; i ++ ) {
    for (int j = 0; j <= m; j++ ) {
        for(int k = 0; k <= s[i] && k * v[i] <= j; k ++ ) {
            dp[i][j] = max(dp[i][j], k * w[i] + dp[i - 1][j - v[i] * k]);
        }
    }
}

由于有个数限制，因此无法像完全背包那样去优化

二进制优化

原理复杂

某物品最多有s件，我们需要从所有的物品中选择若干件，使这个背包的价值最大。没有说某物品一定需要选多少件出来，也没有说一共要选多少件出来。只是选择若干件，至于选几件，无所谓，但要保证价值最大。

如果某物品最多k件，那么像上面我们还需要做k次循环，但是我们果真需要完全遍历一遍吗？实则不然。因为从1-k中的k个数，我们只需要用logk个数就可以表示出来。（如同任何一个数都可以用2的多少次幂相加得到）

所以做法是：某物品有s件，我们把它分成了好几个大的物品。第一个大物品包含1件该物品，第二个大物品是包含2件该物品，第三个大物品是包含4件该物品，第四个大物品是包含8件该物品,…..依次类推。

对所有种类的物品都这么表示出来，那么对于初始每个物品最多s件，我们就把这个件数条件给消去了，然后我们只需要从新的物品中中任意选择（每种物品选或不选），就可以得到原来问题的每种物品选几件的目的。

从而变成01背包问题

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
int cnt = 0;
for(int i = 1; i <= n; i ++ ) {
  int a, b, s; // v, w, s
  cin >> a >> b >> s;
  int k = 1;
  while(s >= k)
  {
    cnt++;
    v[cnt] = a * k;
    w[cnt] = b * k;
    s -= k; // s 是剩余的个数
    k *= 2;
  }
  if(s > 0)
  {
    cnt++;
    v[cnt] = a * s;
    w[cnt] = b * s;
  }
}

// 01 bag
n = cnt;
for(int i = 1; i <= n; i ++ ) {
  for(int j = m; j >= v[i]; j--) {
    dp[j] = max(dp[j], dp[j - v[i] + w[i]]);
  }
}

return dp[m];

分组背包

分成几组，每组中只能选一个

f[i][j]本身表示从前i组物品里面选，总体积不超过j的最大价值

而状态计算的时候，则是将集合划分，将f[i][j]的集合划分出来，枚举的是第i组物品选哪一个。

也就是说f[i][j]，可以由这些情况得来：第i组物品不选，第i组物品选择第一个，，，，

1
2
3
4
5
6
7
8
9
for(int i = 1; i <= n; i ++ ) {
  for(int j = m; j >= 0; j--) {
    for(int k = 0; k <= m; k ++ ) {
      if(v[i][k] <= j) {
        dp[j] = max(dp[j], w[i][k] + dp[j - v[i][k]]);
      }
    }
  }
}

线性DP

递推方程有一个明显的线性关系。

多维状态，求的时候有一个明显的顺序

数字三角形

  • 状态表示：对三角形分行列，易知维数。

    • 集合f[i][j]表示的是什么？——所有从起点开始，走到(i, j)这个点的路径。
    • 属性：上述路径和的最大值

  • 状态计算：集合划分：来自左上方的和来自右上方的

tips：当计算中涉及到了f[i - 1]这种情况的时候，一般让i从1开始，不用处理边界

时间复杂度：状态的数量 * 转移一次的数量

f[i][j] = a[i][j] + max(f[i - 1][j - 1], f[i - 1][j]);

注意：初始化时候，需要多初始化一列，因为最右边的一列需要用到更右边的一列，尤其是有负数的时候。

最长递增子序列

  • 状态表示：一维即可

    • 意义：以第i个数结尾的上升子序列的集合
    • 属性：上述最大长度

  • 状态计算

    • 最后一个数已经以i结尾了，所以划分区间时需要考虑第i - 1个数
    • 第i - 1个数是几，如果第i - 1个数是 j 的话， 那么f[i] = f[j] + 1
1
2
3
4
5
6
7
8
for(int i = 1; i <= n; i ++ ) {
  dp[i] = 1;
  for(int j = 1; j < i; j ++ ) {
    if(a[j] < a[i]) {
      dp[i] = max(dp[i], dp[j] + 1);
    }
  }
}

最长递增子序列II

上述的算法时间复杂度为O(n^2)，能否继续优化？

对于序列3 1 2 5来说，先看序列长度为1的子序列，3和1，但是我们发现后面的数，如果能够接在3后面，那么也一定能够接在1后面，并且1更小，情况更好。所以3就没必要存下来了。

求到第i个数，前面的所有序列可以按照长度分类。长度为n的上升子序列，只需要存储一个结尾最小的子序列。

因此可以存储前面的每种长度的上升子序列的结尾的最小值。且随着长度的增加，其结尾的值也递增。

在这种情况下，如果想求一下以a[i]结尾的最长上升子序列，只需要在上面的数组中，找到最后一个小于a[i]的数，然后+1即可。而找到小于ai的最大值，只需要二分即可。再更新q[i + 1]即可

1
2
3
4
5
6
7
8
9
10
for(int i = 1; i <= n; i ++ ) {
  int l = 0, r = len;
  while(l < r) {
    int mid = l + r >> 1;
    if(f[mid] < a[i]) l = mid;
    else r = mid - 1;
  }
  len = max(len, r + 1);
  f[r + 1] = a[i];
}

最长公共子序列

  • 状态表示：由于两个序列，需要二维（经验 ）
    • f[i][j]意义：所有在第一个序列的前i个字母中出现，且在第二个序列的前j个字母中出现的公共子序列
    • 属性：上述最大长度
  • 状态计算：
    • 选不选a[i]或者b[j]，四个子集合
    • a[i]和b[j]都不选：f[i - 1][j - 1]
    • a[i]和b[j]都选：f[i - 1][j - 1] + 1
    • a[i]不选，b[j]选，所以a[i]不出现在子序列当中，但是b[j]一定出现在公共子序列当中的情况，注意这个集合不等于f[i - 1][j]， f[i - 1][j]指的是在第一个序列的前i - 1个字母中出现，且在第二个序列的前j个字母中出现的公共子序列最大值，也就是说f[i - 1][j]其实可能不会选j，是包含了前面我们想要的情况的。但是我们注意到，后者完全包含前者，而我们要求的是最长公共子序列长度，后者又被包含在f[i][j]中，即从集合个数上来讲，前者小于后者。当我们想在所有情况里选出最大值时，某元素可能会重叠出现在多个情况中，但是对于求最大值来说，是没有影响的。因此是可以使用后者等价替代前者的
    • a[i]选，b[j]不选同上
    • 同时我们又注意到第一种情况被后面的情况包含，因此可以忽略
  • dp[i][j] = max(dp[i - 1][j - 1], max(dp[i - 1][j], dp[i][j - 1]));

最短编辑距离

  • 状态表示：
    • 意义：f[i][j] : 所有将a[1 - i]变成b[1 - j]的方式的集合
    • 属性：操作的最小值
  • 状态计算：

区间dp

合并石头

  • 状态表示：二维
    • 集合：将第i堆石头到第j堆石头合并为一起的合并方式
    • 属性：最小
  • 状态计算：
    • 逻辑上划分的第一步（或者实际操作的最后一步）一定是将最后剩下的两堆合并在一块，因此状态划分可以以最后一次分界线为依据去划分
    • 最后一步的最小代价，就是先合并左边的最小代价，加上右边的最小代价，最后再加上这两堆的总重量（i到j的重量和——前缀和）
    • 区间dp需要注意一点：每次计算f[i][j]时，要确保他的所有子情况都已经准备好了，而最小的子情况是长度为1的情况。所以我们需要先循环区间的长度，再循环起点，就可以达到长度由小到大了
1
2
3
4
5
6
7
8
9
for(int len = 2; len <= n; len ++ ){
  for(int start = 1; start + len - 1 <= n; start ++ ) {
    int i = start, j = start + len - 1;
    dp[i][j] = 1e8;
    for(int k = i; i <= j - 1; k ++ ) {
      dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + s[j] - s[i]); // s is prefix sum
    }
  }
}

计数DP

整数划分

正整数 n 可以表示成若干个正整数之和，n 共有多少种不同的划分方法

完全背包思路

将n看作为容量为n的背包，每个数字都是一个物品，要刚好装满背包。由于每个数字可以用多次，所以是完全背包问题。

  • 状态表示：二维
    • 集合：考虑选前i个数字，刚好和为j的集合
    • 属性：集合大小
  • 状态计算：
    • 用完全背包的思路，dp[i][j] = dp[i - 1][j] + dp[i][j - i]

another idea

  • 状态表示：二维f[i][j]
    • 集合：考虑总和为i，且使用了j个数字的集合（j<=i）
    • 属性：集合大小
  • 状态计算：
    • 分为两大类：j个数字中至少有一个数字1的，以及j个数字里一个数字1都没有的
      • 对于至少有一个1的，我们可以先把这个1去了，对应的集合为f[i - 1][j - 1]，因为去掉一个1后，相当于总和变为i - 1，同时数字也少了一个
      • 对于没有数字1的，说明所有数字都是大于1的，这时我们把所有数字都减去1，还是一个集合，对应f[i - j][j]
      • 最后的结尾需要把总和为n的不同组合数加起来
Geek
#技术 #算法 #Developer #Programming
Algorithms
https://blogoasis.github.io/post/e67bc23f.html
作者
phInTJ
发布于
2022年10月13日
许可协议