Acwing - 算法基础课 - 笔记（动态规划 · 三）

动态规划（三）

本节也是以例题讲解形式为主，主要包括了：数位统计DP，状态压缩DP，树形DP，记忆化搜索。

数位统计DP

计数问题

题目链接

给定两个数a和b，求解a和b之间的所有数字中0-9出现的次数。

比如a=10，b=13，则a和b之间共有4个数：

10，11，12，13

其中，0出现1次，1出现5次，2出现1次，3出现1次。

这道题更像是一道奥数问题，最重要的一步是：分情况讨论。

先考虑实现一个函数：count(n,x)，其表示在1到n中，x出现的次数（x是0-9）

那么，可以用类似前缀和的思想，来求解a到b中，x出现的次数：

count(b,x) - count(a-1,x)

那么先来看，求解count(n,1)，即1到n中，x=1出现的次数。

比如n是个7位的数字 abcdefg，我们可以分别求出1在每一位上出现的次数，然后做一个累加即可。

求1在第4位上出现的次数

即求解有多少个形如xxx1yyy的数字，恰好在1和abcdefg之间。

分情况讨论即可

• 当xxx取值是000到abc - 1之间，此时，第四位取1，后面3位yyy可以随便取（得到的数一定小于abcdefg）。

  即，当xxx = 000 ~ abc - 1时，yyy = 000 ~ 999

  一共是abc * 1000 种组合方式

• 当xxx恰好等于abc，此时又要分情况讨论

  • 当d < 1，此时abc1yyy > abc0efg，此时的次数是0
  • 当d = 1，此时yyy只能取000 ~ efg，此时次数为efg + 1
  • 当d > 1，此时abc1yyy，后面的yyy可以取任意值，即000 ~ 999，此时次数为1000

把上面全部的情况，累加起来，就是1出现在第四位的次数。

类似的，可以求解出1在任意一个位置上出现的次数，累加起来，就求出了1在每一位上出现的此时，即求解出了count(n,1)。

进一步，能够求解出count(n,x)

需要注意一下边界问题：当x=0时，不能有前导0，所以当x=0时，形如xxx0yyy，前面的xxx是从001到999，特别要注意前导0的 特判，当x=0时，循环不能从最高位开始，要从第二位开始。

放一个我认为比较好的题解：https://www.acwing.com/solution/content/52109/

这个题目可以看算法提高课数位DP章节的总结

#include <iostream>
#include <cmath>
using namespace std;

// 获取一个数的位数
int get(int x) {
    int n = 0;
    while(x) n++, x /= 10;
    return n;
}

// 1~n 中, 数字 i 出现的次数
int cnt(int n, int i) {
    int d = get(n), res = 0;
    // 枚举每一个位, 统计 i 出现的次数
    for(int j = 1; j <= d; j++) {
        // abcdefg
        // 假设当前枚举的是d这个位置, l = abc , r = efg, dj = d
        int p = pow(10, j - 1), l = n / p / 10, r = n % p, dj = n / p % 10;
        // 若 i > 0, 则 (000 ~ abc-1) * (000 ~ 999)
        if(i) res += l * p;
        // 若 i = 0, 则 (001 ~ abc-1) * (000 ~ 999)
        else res += (l - 1) * p;
        // 前3位是 abc 时, 看第四位 d 和 i 的相对大小关系
        // 若 d < i, 则这个位置不可能放 i 了, 此时次数为0
        // 若 d = i, 则次数为 000 ~ efg, 共 efg + 1 次
        // 若 d > i, 则次数为 000 ~ 999
        if(dj == i) res += r + 1;
        else if(dj > i) res += p; 
    }
    return res;
}

int main() {
    int a, b;
    while(cin >> a >> b, a) {
        if(a > b) swap(a, b);
        for(int i = 0; i <= 9; i++) printf("%d ", cnt(b, i) - cnt(a - 1, i));
        printf("\n");
    }
    return 0;
}

状态压缩DP

蒙德里安的梦想

题目链接

核心思路：先放横着的，再放竖着的。

总方案数，等于只放横着的小方块的合法方案数。（放完横着的方块之后，竖着的只能被动填充进去）

如何判断，当前方案是否合法？

方案合法的条件是：当横着的方块放完后，竖着的小方块恰好能把剩余的地方全部填满。

那如何判断方案是否合法呢？即怎么看竖着的小方块是否能把剩余部分填满呢？因为是竖着放的，所以可以按列来看，每一列的内部，只要所有连续的空余小方块的个数为偶数，即可。

这道题的f[i,j]比较难。

我们用f[i,j]表示，已经将前i-1列摆好，且从i-1列，伸出到第i列，状态是j，的所有方案。

什么叫做，从第i-1列，伸出来到第i列呢，如下图，第i列的第1，2，5个格子，是从i-1列伸过来的。此时的状态j为 $11001_2$ ，即对于第i列的所有格子，第1，2，5个格子被伸出来占据了（j是个二进制数，若该列的某一行，有伸出来，则用1表示，否则用0表示）。

如上图所示，i = 2，j = 11001，此时的f[i,j]表示的就是，前i - 1列已经摆好，且从第i-1列，伸出到第i列的状态是j时，的全部方案数。（j用二进制来表示第i列的状态，但是我们写代码时，还是按照十进制的值来进行存储）。

这是一个化零为整的过程，因为前i-1列可以任意摆放，所以用f[i,j]一个状态，表示了很多种方案。

状态的表示搞定了，接下来是状态转换。

之前有说过，状态转换，通常是考虑最后一步的情况，根据最后一步的操作来进行分类，我们考虑f[i - 1][k]，即在i-1列的所有可能状态，f[i][j]一定是由某些f[i - 1][k]转移过来的，那k需要满足什么条件，才能够从f[i - 1][k]转移到f[i][j]呢？

首先，f[i - 1][k]，从i - 2列伸出到i - 1列的位置，不能和f[i][j]的那些伸出的位置冲突。如何判断这一点呢？由于是否伸出我们使用二进制位的1来表示，所以只需要对状态k和j做一下与操作，如果伸出的位置没有冲突，则j和k的所有二进制位中，不会在某一个位置，都是1的，即j & k 的结果等于0，就表明了k和j是不会冲突的。这是第一个条件。其次由于f[i][j]的含义中，包含了：前i - 1列已经全部摆好，所以第i - 1列已经是摆好了的，所以i - 1列剩余的连续空格子数，必须是偶数才行，那么此时i - 1列的状态是j | k，需要判断这个状态是否是合法的即可。

我们对于每个状态k，可以预处理出，这个状态的二进制表示中，所有连续0的个数是否是偶数（若所有连续0的个数是偶数，则我们称该状态为合法状态），我们用一个布尔数组st[k]来记录这个信息，当st[k] = true时，表示状态k是合法的。

最后的答案f[m,0]，列是从0到m-1。

化零为整：用一个f[i,j]来表示一堆方案

化整为零：对f[i,j]进行状态转移时，进行情况划分

代码如下：（朴素版）

#include <iostream>
#include <cstring>
using namespace std;

const int N = 12, M = 1 << N;

bool st[M]; // 存储状态是否合法, 当st[i] = true, 表示状态i合法, 合法的含义是: i的二进制表示, 连续0的个数都是偶数

long long f[N][M];

int n, m;

int main() {
	while(true) {
		scanf("%d%d", &n, &m);
		if(n == 0 && m == 0) break;

		// 预处理 st 数组
		for(int i = 0; i < 1 << n; i++) {
			st[i] = true;
			int cnt = 0; // 从二进制位的最低位开始统计连续0的个数
			for(int j = 0; j < n; j++) {
				if(i >> j & 1) { // 当前二进制位是1, 终止统计, 并判断此时连续0的个数
					if(cnt & 1) { // 连续0的个数为奇数, st[i]置为false, 并直接跳过后续计数
						st[i] = false;
						break;
					} // 若连续0的个数是偶数, 则继续进行下一轮计数, 此时cnt不需要清0, 不影响后续计数的
				} else cnt++; // 当前二进制位是0, 进行计数
			}
			if(cnt & 1) st[i] = false;  // 对最后一段连续0的个数的判断, 因为已经结束循环了
		}

		memset(f, 0, sizeof f);
		f[0][0] = 1; // 初始化, 从第-1列伸出到第0列, 且状态是0的方案数是 1
		for(int i = 1; i <= m; i++) { // 从第1列开始处理, 到第m列
			for(int j = 0; j < 1 << n; j++) { // 枚举第i列全部可能的状态, 从000...00, 到111...11
				for(int k = 0; k < 1 << n; k++) { // 枚举第 i-1列可能的状态k, 看能否从k转移到j
					if((j & k) == 0 && st[j | k]) { // 能够从k转移到j, 则方案数累加
						f[i][j] += f[i - 1][k];
					}
				}
			}
		}

		printf("%lld\n", f[m][0]);
	}
	return 0;
}

优化版：针对某一种状态j，我们可以预处理出有哪些合法状态k，可以从k转移到j

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int N = 12, M = 1 << N;

bool st[M];

long long f[N][M];

int n, m;

vector<int> vs[M]; // 对于状态j, vs[j] 存储的是一个数组, 数组中每个元素, 都是能够转移到 j 的有效状态

int main() {
	while(true) {
		scanf("%d%d", &n, &m);
		if(n == 0 && m == 0) break;

		// 预处理
		for(int i = 0; i < 1 << n; i++) {
			st[i] = true;
			int cnt = 0;
			for(int j = 0; j < n; j++) {
				if(i >> j & 1) {
					if(cnt & 1) {
						st[i] = false;
						break;
					}
				} else cnt++;
			}
			if(cnt & 1) st[i] = false;
		}

		for(int i = 0; i < 1 << n; i++) {
			vs[i].clear(); //清除, 因为要重复使用
			for(int k = 0; k < 1 << n; k++) {
				if((i & k) == 0 && st[i | k]) vs[i].push_back(k);
			}
		}

		memset(f, 0, sizeof f);
		f[0][0] = 1;
		for(int i = 1; i <= m; i++) {
			for(int j = 0; j < 1 << n; j++) {
				for(auto k : vs[j]) { // 直接遍历有效状态, 进行累加即可
					f[i][j] += f[i - 1][k];
				}
			}
		}

		printf("%lld\n", f[m][0]);
	}
	return 0;
}

最短哈密顿路径

题目链接

先来想一下暴力的解法，由于任意两个点之间都有边，所以一个哈密尔顿路径就是把0~n-1个点的一次排列。则全部的哈密尔顿路径个数为n!
而针对每条哈密尔顿路径，求解一下其长度，需要n次计算。则全部的时间复杂度就是 n!×n。太高了。
我们考虑用动态规划来做。用和上一题类似的思想。
我们考虑f[i][j]，用f[i][j]来表示，从0号点，走到j号点，且中间经过的点的状态是i（用二进制来表示，比如经过0号点，2号点，最终到达2号点，则状态i为101，j为2）的全部的路径的集合。
接下来考虑f[i][j]的值，它应该表示这些路径中的最短路径长度。
状态的表示我们考虑结束，接下来考虑一下状态转移。还是根据最后一步来进行划分。我们最后一个点是j，我们考虑倒数第二个点k，根据倒数第二个点是0到n-1，来划分集合。
需要注意的是，状态i去掉j点后，仍需要包含点k，才能转移过来。
则状态转移方程为：
f[i][j] = min(f[i 去掉 j][k] + w[k][j])
先从0号点走到k号点，最后一步再从k号点走到j号点。

#include <iostream>
#include <cstring>
using namespace std;

const int N = 20, M = 1 << N;

int g[N][N], f[M][N];

int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) cin >> g[i][j];
    }

	// 初始化f为正无穷
    memset(f, 0x3f, sizeof f);
    // 经过第一个点，即0号点，走到0号点，距离为0
    f[1][0] = 0;

	// 遍历全部的状态
    for(int i = 1; i < 1 << n; i++) {
    // 遍历所有点
        for(int j = 0; j < n; j++) {
        	// 当状态i包含j号点时，才有意义，不然根本都走不到j号点
            if(i >> j & 1) {
            	// 遍历倒数第二个点k
                for(int k = 0; k < n; k++) {
                	// 把状态i中除掉j号点，如果还包含k号点, 则说明可以转移过来
                    if((i - (1 << j)) >> k & 1) f[i][j] = min(f[i][j], f[i - (1 << j)][k] + g[k][j]);
                }
            }
        }
    }
	// 最终答案是
	// 走过0~n-1这n个点（状态i每个位置都是1），最终到达n-1号点的最短路径
    printf("%d\n", f[(1 << n) - 1][n - 1]);
    return 0;
}

------- 2022/06/02 更新

重刷最短哈密尔顿路径时，发现在dp的状态计算时，如果把外层循环和内层循环交换，得到的就是WA。即，外层循环必须是枚举全部状态，内层循环必须是枚举所有点，不能颠倒过来，至于为什么，有待研究…

在讨论区和题解区逛了一下，大概知道了。状态计算时，需要依赖前一个状态。如果外层循环是枚举的点，那在计算某个点j的状态f[i][j]时，要依赖路径上的前一个点，这个前一个点，可能比j要大，或者比j小，他俩关系不是确定的，而外层循环是从小到大枚举点（从大到小枚举也一样），这个被依赖的点的状态可能还没有被计算过。

而当前状态i，依赖的前一个状态一定是比i小的，因为要从状态表示中减掉当前的节点，会使得状态表示变小，所以我们可以先计算状态更小的全部节点的状态，就能保证在后续的状态转移中，所依赖的状态全部都已经被计算过。故外层循环必须从小到大枚举状态。

树形DP

没有上司的舞会

题目链接

状态转移方程大概说一下：

假设节点 $u$ 有 $N$ 个子节点，则

f ( u , 0 ) = ∑ 1 n m a x { f ( s i , 0 ) , f ( s i , 1 ) } f(u, 0) = \sum_1^n max\{ f(s_i,0), f(s_i,1) \} f(u,0)=∑1n​max{f(si​,0),f(si​,1)} ，由于0表示 $u$ 这个节点不选，则其每个子节点取最大值，即取 m a x { f ( s , 1 ) , f ( s , 0 ) } max \{ f(s,1), f(s,0)\} max{f(s,1),f(s,0)}，然后累加即可

而1 表示 $u$ 这个节点要选，则其子节点都不能选，所以

$f(u,1)=happ{y}_u+{\sum }_1^{n}f(s_i,0)$

用DFS+DP

#include <iostream>
#include <cstring>
using namespace std;

const int N = 6010;

int h[N], e[N], ne[N], idx; //图的邻接表存储

int happy[N];

bool has_father[N]; // 是否存在父节点, 用于找出树根

int n;

int f[N][2];

void add(int a, int b) {
    // 添加一条边 a -> b
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx++;
}

void dfs(int x) {
    // f[x][0] = 0, f[x][1] = happy[x]
	f[x][1] = happy[x];
	for(int i = h[x]; i != -1; i = ne[i]) {
		int u = e[i];
		dfs(u);
		f[x][0] += max(f[u][0], f[u][1]);
		f[x][1] += f[u][0];
	}
}

int main() {
	memset(h, -1, sizeof h);
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", &happy[i]);

	for(int i = 0; i < n - 1; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		add(b, a); //b -> a , b为父节点, 表示上级
		has_father[a] = true;
	}

	// 找出树根
	int root;
	for(int i = 1; i <= n; i++) {
		if(!has_father[i]) {
			root = i;
			break;
		}
	}

	dfs(root);

	printf("%d\n", max(f[root][0], f[root][1]));

	return 0;
}

------2022/06/02 更新
今天炒回锅肉，重新做的过程中，发现了自己错误的思路。先贴出来，如下：

状态表示：

f[i][0] : 从1-i个职员中选, 且不选第i个职员, 能得到的最大快乐值
f[i][1] : 从1-i个职员中选, 且选第i个职员, 能得到的最大快乐值

答案 = max{ f[n][0], f[n][1] }

状态转移: 

f[i][0] = max { f[i - 1][0], f[i - 1][1] }

f[i][1] =  max { f[i - 1][0], f[i - 1][1] } + h[i]   （当 i 和 i - 1 没有上下级关系）
        =  f[i - 1][0] + h[i]                        （当 i 和 i - 1 有上下级关系）

错误代码：

#include <iostream>
using namespace std;
const int N = 6010;
int h[N]; // happy index
int p[N]; // parent
int n, l, k;
int f[N][2];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i < n; i++) {
        cin >> l >> k;
        p[l] = k;
    }

    f[1][0] = 0;
    f[1][1] = h[1];

    for (int i = 2; i <= n; i++) {
        f[i][0] = max(f[i - 1][0], f[i - 1][1]);
        if (p[i] == i - 1 || p[i - 1] == i) {
            // 若 i 和  i - 1 存在上下级关系
            f[i][1] = f[i - 1][0] + h[i];
        } else {
            f[i][1] = max(f[i - 1][0], f[i - 1][1]) + h[i];
        }
    }

    printf("%d\n", max(f[n][0], f[n][1]));
    return 0;
}

用例：

1 2 3 4 5    6 7   （职工编号）
1 1 1 1 -128 1 1  （快乐值）

  上下级关系：
 
        5
     4      3 
  6    7   1  2

状态计算过程

 f[1][0] = 0, f[1][1] = 1 (选1)
 f[2][0] = 1, f[2][1] = 2 (选1,2)
 f[3][0] = 2, f[3][1] = 2 (选1,3) (这里已经错了)
 f[4][0] = 2, f[4][1] = 3
 f[5][0] = 3, f[5][1] = -126
 f[6][0] = 3, f[6][1] = 4
 f[7][0] = 4, f[7][1] = 5

上面错误思路的关键在于，没有从树根往下进行计算（而是编号从小到大进行计算），导致前面已经计算好的状态，可能和后面的状态冲突（比如上面的样例）。

正确的做法应该是用类似DFS的形式，从树根开始，对这棵树进行深搜。

下面贴一个自己重做时，修正思路后的代码，跟最开始的代码有点不一样，有点记忆化搜索那味儿。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 6010;
int ha[N]; // happy index
int h[N], e[N], ne[N], idx; // 树的邻接表表示
int n, l, k;
int f[N][2];

void add(int a, int b) {
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}

int dfs(int x, int st) {
    // 有点记忆化搜索那味儿了
    if (f[x][st] != -1e9) return f[x][st];
    
    int sum = st == 0 ? 0 : ha[x];
    
    for (int i = h[x]; i != -1; i = ne[i]) {
        int u = e[i];
        if (st == 0) sum += max(dfs(u, 0), dfs(u, 1));
        else sum += dfs(u, 0);
    }
    
    f[x][st] = sum;
    
    return sum;
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> ha[i];
        f[i][0] = f[i][1] = -1e9; // 初始化为-INF
    }
    int root = 0;
    for (int i = 1; i < n; i++) {
        cin >> l >> k;
        add(k, l);
        root += i;
        root -= l;
    }
    root += n;
    // 先从 1 + 2 + 3 + ... + n
    // 再减去所有以儿子身份出现过的节点, 共 n - 1个, 剩下的那个就是根节点
    
    // 从树根开始, 搜索
    printf("%d\n", max(dfs(root, 1), dfs(root, 0)));
    
    return 0;
}

记忆化搜索

滑雪

题目链接

使用递归的方式来实现。

记忆化搜索的代码复杂度比较低，但是可能运行会慢一些些，然后如果递归深度比较深的话，可能会爆栈。

#include <iostream>
#include <cstring>
using namespace std;

const int N = 310;

int f[N][N];

int s[N][N];

int r, c;

int dx[4] = {1, -1, 0, 0};

int dy[4] = {0, 0, 1, -1};

int dp(int x, int y) {
	if(f[x][y] != -1) return f[x][y];
	int res = 1;
	for(int i = 0; i < 4; i++) {
		int nx = x + dx[i], ny = y + dy[i];
		// 滑过去的区域是有效的
		if(nx >= 1 && nx <= r && ny >= 1 && ny <= c && s[nx][ny] < s[x][y]) {
			res = max(res, dp(nx, ny) + 1);
		}
	}
	f[x][y] = res;
	return f[x][y];
}

int main() {
	memset(f, -1, sizeof f);
	scanf("%d%d", &r, &c);
	for(int i = 1; i <= r; i++) {
		for(int j = 1; j <= c; j++) scanf("%d", &s[i][j]);
	}

	int res = 1;
	for(int i = 1; i <= r; i++) {
		for(int j = 1; j <= c; j++) {
			res = max(res, dp(i, j));
		}
	}
	
	printf("%d\n", res);

	return 0;
}