基础动态规划

$Dynamic\ Programming$

动态规划分析：

主要思想：

类似于递推，将当前状态的属性（最大值 $max$，最小值 $min$，解的个数 $nums$）由上一个状态转移而来，从而继承上一个状态的属性，具有最优子结构属性，由此得出状态转移方程

dp的状态转移方程可以有两种思考方式：顺推和逆推

顺推即考虑当前状态能向后推出何状态
逆推即考虑当前状态由哪些状态转移而来

状态转移方程的推导方式

openjudge4008-糖果

顺推：

f[i + 1][j] = f[i][j];
// 不选当前第 i + 1 件物品
f[i + 1][(j + a[i + 1] % k)] = f[i][j] + a[i + 1];
// 选当前第 i + 1 件物品

值得注意的是，在顺推中 $f_{i, j}$ 表示未计算 $i, j$ 值的状态，因此顺推的目标解为 $f_{n + 1, k}$

逆推：

f[i][j] = f[i - 1][j];
// 不选当前第 i 件物品
f[i][j] = f[i - 1][((j - a[i]) % k + k) % k] + a[i];
// 选当前第 i 件物品， + k % k 意在保证下标的恒正性

对于两种状态取 $max$ 即可

同时，该状态需要具有无后效性的特点，即当前状态的选择无法影响下一状态的决策

另外值得注意的是，我们需要对dp边界的初始值进行特判

动态规划问题的时间复杂度分析:

状态数量 * 转移计算量

背包问题：

给定 n 个物体，和一个容量是 v 的背包，每个物体的体积是vi，权重是 wi，，求如何装物品使得总权重最大

在背包问题中，f[i][j]表示所有从前i个物品中选并且总体积不超过j的所有选法中最大/最小的总价值

经典背包问题特点

背包问题	特点
01背包	每件物品最多只能用一次
完全背包	每件物品可以用无限次
多重背包	每件物品可以使用有限次
分组背包	将所有物品分为若干组每组物品中最多只能选一个物品

01背包

acwing2-01 背包问题

朴素解：

int n, m;
// n 表示所有物品的个数，m 表示背包容量
int v[N + 10], w[N + 10];
// v 表示各个物品所占的体积，w 表示各个物品的价值
int f[N + 10][N + 10];
// 状态方程，存储当前价值最大值

    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
        cin >> v[i] >> w[i];

    // for (int j = 0; j <= m; j ++) f[0][j] = 0;
    // 一件物品都不选，可省略 
    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
        {
            f[i][j] = f[i - 1][j];
            // 不取 i 的情况
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
            // 能够装下 i 时取 i 的情况 
        }
    cout << f[n][m] << endl;

在 dp 每一层的状态计算中不难发现，每一层第一维度的值都和上一层的值有关 f[i][j] = f[i - 1][j] ，第二维度的值只可能出现 j 或 j - v[i]，那么可以利用滚动数组对空间进行优化：

for (int i = 1; i <= n; i ++)
    for (int j = m; j >= v[i]; j --)
        // f[i][j] = f[i - 1][j];
        // if (j >= v[i]) j 直接从 v[i] 开始，则无需判断
        f[j] = max(f[j], f[j - v[i]] + w[i]);
        // 将 j 倒序计算，则可以保证 j - v[i] 为 i - 1 层的值

cout << f[m] << endl;

完全背包

完全背包的状态计算：

类比于01背包将当前情况分为选(1)或不选(0)，在完全背包中可以按照选多少个物品分类

对于各个集合中状态的表示，设当前物品选了 k 个，即有状态转移方程：
f[i - 1][j - k * v[i]] + k * w[i]

将每个情况取最大值，即可求出当前情况的价值最大值

朴素解：

int n, m;
int v[N + 10], w[N + 10];
int f[N + 10][N + 10];

cin >> n >> m;
for (int i = 1; i <= n; i ++) cin >> v[i] >> w[i];

for (int i = 1; i <= n; i ++)
    for (int j = 1; j <= m; j ++)
        for (int k = 0; k * v[i] <= j; k ++)
        // 枚举物品数量，保证总体积不超过 j 
            f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
				
	cout << f[n][m] << endl;

一维优化：

当对 f[i][j] 进行枚举时，进行的过程是这样的：

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

在枚举 f[i][j] 时，我们已经完成了对 f[i, j - v[i]] 的枚举，当时进行的过程是这样的：

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

此时我们发现，计算 f[i][j] 的过程与计算 f[i][j - v[i]] 的过程非常相似，规律可以表述为：

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

那么我们可以将状态转移方程优化为：

for (int i = 1; i <=n; i ++)
    for (int j = 0; j <= m; j ++)
    {
        f[i][j] = f[i - 1][j];
        if (j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
    }

此时的状态转移方程为：
f[i][j] = max(f[i][j], f[i][j - v[i] + w[i]])

而在01背包中的状态转移方程为：
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i] + w[i]])

类比于01背包的一维优化，我们可以将完全背包优化为：

1
2
3

for (int i = 1; i <=n; i ++)
    for (int j = v[i]; j <= m; j ++)
        f[j] = max(f[j], f[j - v[i]] + w[i]);

到此为止，我们已经将完全背包的时间复杂度优化到了 $O(n)$

多重背包

对于每个物品都有个数限制 s[i]，只需枚举物品个数 $k$ 并使 $k$ 满足
k <= s[i] && k * v[i] <= j

朴素版本：

int n, m;
int v[N + 10], w[N + 10], s[N + 10];
int f[N + 10][N + 10];
	cin >> n >> m;
	for (int i = 1; i <= n; i ++)
        cin >> v[i] >> w[i] >> s[i];
	
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
			for (int k = 0; k <= s[i] && k * v[i] <= j; k ++)
			// 保证总体积不超过 j 的同时使 k 不超过限制个数
				f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
				
	cout << f[n][m] << endl;

多重背包的二进制优化 $O(w·n·logs)$：

基本原理：

假设s = 1023，如按照朴素方式枚举，则需要枚举 1023 次。此时我们将 1 ~ 1023 分为十组，每组分别是：

2^0^, 2^1^, 2^2^, 2^3^, …, 2^9^

即：1, 2, 4, 8, …, 512

易证对于 [1, 1023] 区间中的每一个数字，都可以用以上 10 个数表示

当 $s$ 不为 2 的正整数次方时，假设 s = 200，此时我们将 200 分为以下几组：

2^0^, 2^1^, 2^2^, 2^3^, 2^4^, 2^5^, 2^6^, 73

此时即可以用以上几组数据将 [1, 200] 区间中所有的数字表示出来

将 $s$ 推广为一般数字：

2^0^, 2^1^, 2^2^,…, 2^k^, s - 2^k^

由此可知，对于任意一个 $s$ ，都可以拆分为 log2s 个组, 只需要找到这 log2s 个组所有排列组合的最大值，即为这几个组的 01背包 问题

模板：

const int N = 25000;
// 一共有 1000 项，每项最多拆分成 log s项  
const int M = 2010;

int n, m;
int v[N], w[N];
int f[N];

cin >> n >> m;

int cnt = 0;
for (int i = 1; i <= n; i ++)
{
    int a, b, s;
    cin >> a >> b >> s;
    
    for (int k = 1; k <= s; k *= 2)
    // 从2^0 开始枚举 2 的次幂
    {
        s -= k;
        v[++ cnt] = a * k;
        w[cnt] = b * k;
    }
    if (s > 0)
    {
        v[++ cnt] = a * s;
        w[cnt] = b * s;
    }
}
n = cnt;
// 二进制拆分读入
    
for (int i = 1; i <= n; i ++)
    for(int j = m; j >= v[i]; j --)
        f[j] = max(f[j], f[j - v[i]] + w[i]);

cout << f[m] << endl;
// 01背包解题过程

分组背包

将所有物品分为若干组，每组物品中最多只能选一个物品，只需枚举第 $i$ 组中选第 $k$ 物品

可得状态转移方程：
f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k])

(v[i][k] 表示第 $i$ 组物品中第 $k$ 个物品的体积，以此类推)

模板：

const int N = 1e2 + 10;

int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

int main()
{
	cin >> n >> m;
	
	for (int i = 1; i <= n; i ++)
	{
		cin >> s[i];
		for (int j = 0; j < s[i]; j ++)
			cin >> v[i][j] >> w[i][j];
	}
	
	for (int i = 1; i <= n; i ++)
		for (int j = m; j >= 0; j --)
			for (int k = 0; k < s[i]; k ++)
				if (v[i][k] <= j)
					f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
					
	cout << f[m] << endl;
	
	return 0;
}

依赖背包

选 $A$ 物品需要购买 $B$ 物品，或选 $A$ 物品才可以买 $B， C$ 物品

洛谷p1064 - 金明的预算方案

基本的解决思路是，我们将两种绑定的物品转化为分组背包，举个例子，若买 $A$ 之后才可以买 $B$，会出现以下三种情况

选 $A$ 不选 $B$

选 $A$ 选 $B$

不选 $A$ 不选 $B$

对于每一种情况，进行 $dfs$ 深度搜索绑定为一个组，再按照分组背包的二进制解即可

我们可以发现，当有 $n$ 件物品依附于一件物品时，分出组的个数为 $2^n + 1$ 时间复杂度起飞 ~

当物品的绑定关系较为复杂时，可以使用树形DP或图上DP

线性动态规划

经典应用：

1. Acwing895-最长上升子序列

暴力版本 $O(n^2)$

集合：

可以用 f[i] 表示所有以第 $i$ 个数结尾的上升子序列，维护的属性是长度最大值 Max；

那么如何将初始状态转移到 f[i] 呢？

我们可以依照 f[i] 子序列的倒数第二个数来分类： 0 表示当前子序列长度为 1，1 表示该子序列的倒数第二个数为总序列第 1 个数 ……以此类推，直到 i - 1 表示该子序列的倒数第二个数为总序列第 i - 1 个数。

如何判断该状态是否成立呢？

对于 f[i] = j，只需判断 a[j] < a[i]，如成立则存在该状态

因此得到的状态转移方程为：

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

该解法的时间复杂度？

状态数量 O(n) * 转移计算量 O(N) = $O(n^2)$

int n;
int a[N];
int f[N];

cin >> n;
for (int i = 1; i <= n; i ++)
    cin >> a[i];

for (int i = 1; i <= n; i ++)
{
    f[i] = 1;
    // 最长上升子序列至少为 1 ,即为当前数
    for (int j = 1; j <= i - 1; j ++)
        if (a[j] < a[i])
            f[i] = max(f[i], f[j] + 1);
}

int res = -1e9;
for (int i = 1; i <= n; i ++)
    res = max(res, f[i]);

cout << res << endl;

另外，也可以将选当前位置和不选当前位置单独分离出一个二维状态

若要记录最长上升子序列，则将主体部分改为：

int g[N];
// 存储第 i 个点是由哪个下标位置转移而来的

for (int i = 1; i <= n; i ++)
{
    f[i] = 1;
    g[i] = 0;
    // 最长上升子序列至少为 1 ,即为当前数
    for (int j = 1; j <= i - 1; j ++)
        if (a[j] < a[i])
            if(f[i] < f[j] + 1)
            {
                f[i] = f[j] + 1;
                g[i] = j;
                // 更新 f 并记录转移方向
            }
}

int k = 1;
// 记录最长子序列位置的下标
for (int i = 1; i <= n; i ++)
    if (f[k] < f[i])
        k = i;
    // 维护上升子序列长度的最大值

cout << f[k] << endl;
// 输出最长上升子序列长度

for (int i = 0, len = f[k]; i < len; i ++)
{
    cout << a[k] << " ";
    k = g[k];
}
// 倒序输出最长上升子序列

单调优化版：$O(n · logn)$

观察性质可以发现，对于

3 1 2 1 8 5 6

这个序列，当枚举以 8 为结尾的最长上升子序列时，下标为 1 的数字 1 无疑是比下标为 0 的数字 3 更优的选择 (涵盖的值域更大，更有机会取得最长上升子序列)

因此我们可以开一个数组 q[N] 存储长度为 $i$ 的上升子序列中结尾元素最小的情况中结尾元素的值。

该最小值是否随结尾值 $i$ 的增大而严格单调递增？

假设对于长度为 $k$ 的末尾最小值为 $n$ ，若 $n$ 小于或等于等于长度为 $k - 1$ 的末尾的最小值，则对于 $k - 1$ 必有一种更优的、最小值更小的情况，则该假设不成立

那么如何求出以 a[i] 结尾的最长上升子序列的长度的最大值呢？

对于预处理好的不同长度的上升子序列 q，只需在该数组中利用二分查找找到不大于 a[i] 的最大的值 q[k] ，将 a[i] 接在 q[k] 后面即可。此时还要注意，由于 q[k] 是不大于 a[i] 的最大的情况，所以 q[k + 1] 的值一定会大于 a[i] 因此需要更新 q[k + 1]

由于对于每个点进行二分查找，因此该算法的时间复杂度是 $O(n · logn)$

模板：

int n;
// n 表示元素个数
int a[N], q[N];
// a[] 用于存储数列
// p[] 用于维护所有不同长度的最长上升子序列结尾元素的最小值 

cin >> n;
for (int i = 0; i < n; i++)
    cin >> a[i];

int len = 0;
// 存储当前枚举到的最长上升子序列的长度，即 q 数组中的元素个数 
q[0] = -2e9;
// 初始化边界
for (int i = 0; i < n; i ++)
{
    // 二分查找不大于 a[i] 的最大值在 p 中的元素位置
    int l = 0, r = len;
    while (l < r)
    {
        int mid = l + r  + 1 >> 1;
        if (q[mid] < a[i]) l = mid;
        else r = mid - 1;
    }
    // r 返回不大于 a[i] 的最大值的下标(即长度)
    len = max(len, r + 1);
    // 将 a[i] 连接在不大于 a[i] 的最大值的最长上升子序列的后面，表示长度，即 r + 1
    q[r + 1] = a[i];
}

cout << len << endl;

2. Acwing897-最长公共子序列

集合：

使用 f[i][j] 表示所有 第一个字符串的前 $i$ 个字母构成的子序列 和 第二个字符串前 $j$ 个字母构成的子序列 的公共子序列长度

属性：

长度最大值

集合划分：

将全集依照是否选择 a[i] 和 b[j] 分为四个子集：

00：a[i] 与 b[j] 均不选
01：a[i] 选而 b[j] 不选
10：a[i] 不选而 b[j] 不
11：a[i] 与 b[j] 选

状态表示

对于第一种状态，可以表示为 f[i - 1][j - 1]

对于第二种状态，可以表示为 f[i - 1][j]，但由于 f 数组表示的是子序列长度，所以并不能达到 “不包含 a[i] 而包含 b[j] 的情况” 。因此这种情况是包含第一种状态的，但由于所求属性为长度最大值，这种冲突并不会影响最终结果

同理，对于第三种状态，可以表示为 f[i][j - 1]

对于第四种状态，可以表示为 f[i - 1][j - 1]
因此， f 的状态计算只需取后三种情况的最大值即可

模板

int n, m;
char a[N], b[N];
int f[N][N];

cin >> n >> m;
cin >> a + 1 >> b + 1;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j ++)
    {
        f[i][j] = max(f[i][j - 1], f[i - 1][j]);
        if (a[i] == b[j])
            f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
    }
    
cout << f[n][m] << endl;

区间dp

区间dp 就是将若干个集合合并为一个集合，每次合并付出的代价为集合元素个数，求将所有集合合并为一个集合所付出的最小代价

集合：

f[i][j] 表示将所有从第 i 个集合到第 j 个集合合并为一个集合的合并方式

属性

最小值

状态表示

我们可以发现，不论哪种合并方式，最后一步均为将两个集合合并为一个集合，因此可以以最后一次合并集合的分界线分类，即可以将全集分为 k - 1 个部分

由此，第三维度的 $k$ 仅需从 1 枚举到 j - 1 即可

时间复杂度分析

状态的二维转移需要 $O(n^2)$，枚举 $k$ 的时间为 $O(n)$，因此总时间复杂度为 $O(n^3)$

模板

整体思路：先从小到大枚举区间长度，再从前往后枚举区间左端点，最后枚举分割点的决策

const int N = 310;
const int INF = 1e8;

int n;
int s[N], f[N][N];
// s 存储前缀和

cin >> n;
for (int i = 1; i <= n; i ++) cin >> s[i];
// input
for (int i = 2; i <= n; i ++) s[i] += s[i - 1];
// 处理前缀和

for (int len = 2; len <= n; len ++)
// 枚举待合并的区间长度
    for (int i = 1; i + len - 1 <= n; i ++)
    // 枚举区间位置
    {
        int l = i, r = i + len - 1;
        //  取出起始位置 
        f[l][r] = INF;
        // 初始化一个最大值，循环找出最小值 
        for (int k = l; k < r; k ++)
            f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
            // 按合并区间的分界线分类枚举 
    }
cout << f[1][n] << endl;

计数类dp

Acwing900-整数划分

完全背包解

状态表示

f[i][j] 表示从 1 ~ i 中选并且总和等于 $j$ 的所有选法集合

状态转移方程

f[i][j] = f[i - 1][j] + f[i][j - i]

类比于完全背包的一维优化，优化后的状态转移方程：

f[j] = f[j] + f[j - i]

int n;
int f[N];

cin >> n;
f[0] = 1;
for (int i = 1; i <= n; i ++)
    for (int j = i; j <= n; j ++)
        f[j] = (f[j] + f[j - i]) % MOD;
        
cout << f[n] << endl;

其他解法

状态表示

f[i][j] 表示所有总和为 $i$ ，并且恰好表示为 $j$ 个数的和的方案数集合

状态计算

将全集按照所有拆分成的数字分为：

拆分成的数字中最小值为 1
拆分成的数字中最小值不为 1

由此则可以做到状态不重不漏地表示

那么如何表示这两种状态呢？

对于第一种情况，如果将其中的一个 1 删除，则可以从前面的状态转移到此状态且并不影响总方案数，则该状态表示为 f[i - 1][j - 1]

对于第二种情况，如果将所有数都减去 1 ，在能够从前面状态转移到此状态的前提下仍能保证集合中的数均为正整数，则该状态表示为 f[i - j][j]

则有：f[i][j] = f[i - 1][j - 1] + f[i - j][j]

值得注意的是，题目要求输出一个正整数 $n$ 的所有拆分方案，而以上的状态转移方程仅限于正整数 $i$ 拆分为 $j$ 个数，因此对于所有方案的计算，只需：

1 2	for (int i = 1; i <= n; i ++) ans += f[n][i];

正解

int n;
int f[N][N];
int res;

cin >> n;
f[0][0] = 1;

for (int i = 1; i <= n; i ++)
    for (int j = 1; j <= i; j ++)
        f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % MOD;
        
for (int i = 1; i <= n; i ++)
    res = (res + f[n][i]) % MOD;

cout << res << endl;

数位$DP$

AcWing 338.计数问题

情况分析

进行分类讨论

将问题简化，寻找1~n中0~9出现的次数，可以使用前缀和思想
假设是从1~n, x = 1, n = abcdefg
求1在第四位上出现的次数
1 <= xxx1yyy <= abcdefg
1. xxx = 000 ~ abc - 1, yyy = 000 ~ 999, 共abc * 1000种选法
2. xxx = abc时
  1. d < 1, abc1yyy > abc0efg, 共有0种选法
  2. d = 1, yyy = 000 ~ efg, 共有efg + 1种选法
  3. d > 1, yyy = 000 ~ 999, 共有1000种选法

$dp$问题难点在状态表示和分情况讨论

边界情况

当枚举的数字出现在最高位上时，只存在第二种情况
当枚举数字为0时，前三位不能取000

听不懂了，看视频吧

状态压缩$dp$

核心思想是使用二进制数的每一位表示不同的情况或者数据

二进制操作

取出整数n在二进制表示下第k位：(n >> k) & 1
取出整数n在二进制表示下第0 ~ k - 1位(后k位)：n & ((1 << n) - 1)
把整数n在二进制表示下的第k位取反：n ^ (1 << k)
对整数n在二进制表示下的第k位赋值为1：n | (1 << k)
对整数n在二进制表示下的第k位赋值为0：n & (~(1 << k))

例1

AcWing 291.蒙德里安的梦想

时间复杂度$O(4 * 10^7)$

当放入所有横向小方格之后，只剩一种情况来放置竖向的小方格，因此只需求摆放横向小方格的方案数
竖向来分析，f[i][j]代表现在要摆第i列，j使用二进制存储的是上一列种哪些列伸出横向小方格(0代表没有伸出，1代表伸出来了)
在枚举到第i列时，分析第i - 1列的j(记作k)，需要满足
1. (j & k) == 0，即上一列伸出来的和这一列不冲突
2. j | k中不存在连续奇数个0，所有剩余的连续格子都必须是偶数，因为剩下的只能放置竖向小方块

核心代码

int n, m;
while(cin >> n >> m, n || m)
{
    memset(f, 0, sizeof f);

    for(int i = 0; i < 1 << n; i ++)//预处理所有状态不存在连续奇数个0
    {
        st[i] = true; //假设成立 
        int cnt = 0; //表示当前这一段连续0的个数
        for(int j = 1; j < n; j ++)
            if(i >> j & 1) //当前位小方块被填充, 上一个连续段截止
            {
                if(cnt & 1) st[i] = false; //如果是奇数就置为false
                cnt = 0;
            }
            else cnt ++;
            if(cnt & 1) st[i] = false; //判断最后一段
    }
    //以下为dp过程
    f[0][0] = 1; //最开始小方块什么都没有放(指不会受到前面的影响)

    for(int i = 1; i <= m; i ++)
        for(int j = 1; j <= 1 << n; j ++ ) //枚举所有状态 0~2^n
            for(int k = 0; k < 1 << n; k ++) //枚举i - 1列所有状态 0~2^n
                if((j & k) == 0 && st[j | k])
                    f[i][j] += f[i - 1][k];

    cout << f[m][0];
}

例2

AcWing 91.最短Hamilton路径

暴力思路

因为每个点走一次，所以遍历0 ~ n - 1的全排列
时间复杂度$O(n! * n)$, 即$O(20! * 20)$
因此使用状态压缩DP求解

状态压缩DP思路

你看不懂的补充(集合幂级数)

f[i][j]表示所有从0走到j，走过的所有点是i的所有路径 (属性：Min)
用i，一个二进制数的每一位表示每一个点有没有走过
分类依据
根据倒数第二个点的位置分类(从0到n - 1)
假设倒数第二个点是k，路径就是从$0 \rightarrow k \rightarrow j$，其中$k \rightarrow j$已知，只需求$0 \rightarrow k$的最小值即可
其中$0 \rightarrow k$的值应该是f[i - j][k]，其中j代表点，不是直接运算
答案只需循环计算min(f[i][j], f[i - j][k] + a[k][j])

核心代码

//从0开始读入w[i][j] 此处省略
memset(f, 0x3f, sizeof(f));
f[1][0] = 0; //初始位是0
for(int i = 1;i < 1 << n; i ++)
    for(int j = 0; j < n;j ++) //i和j枚举所有状态
        if(i >> j & 1) //保证i包含j, 状态才有意义
            for(int k = 0; k < n; k ++) //枚举所有转移状态，找从哪个点转移过来
                if((i - (1 << j)) >> k & 1) //只有第k位是1的时候才能取到第k位
                    f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
cout << f[(1 << n) - 1][n - 1] << endl;

树形$DP$

AcWing 285.没有上司的舞会

因本题已经熟练掌握，暂时略去本题分析，以后找到其他题再进行分析

代码实现

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 6010;

int n;
int h[N], e[N], ne[N], idx;
int happy[N];
int f[N][2];
bool has_fa[N];

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

void dfs(int u)
{
    f[u][1] = happy[u];

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        dfs(j);

        f[u][1] += f[j][0];
        f[u][0] += max(f[j][0], f[j][1]);
    }
}

int main()
{
    scanf("%d", &n);

    for (int i = 1; i <= n; i ++ ) scanf("%d", &happy[i]);

    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(b, a);
        has_fa[a] = true;
    }

    int root = 1;
    while (has_fa[root]) root ++ ;

    dfs(root);

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

    return 0;
}

记忆化搜索

优点：考虑代码复杂度，使代码复杂度降低，思路简单，便于调试

AcWing 901.滑雪

递归分析动态规划法

闫氏$DP$分析法

状态表示

集合：所有从f[i][j]开始滑的路径
属性：Max
状态计算

向右滑: f[i][j + 1] + 1 前提: h[i][j + 1] < h[i][j]
向左滑: f[i][j - 1] + 1 前提: h[i][j - 1] < h[i][j]
向前滑: f[i + 1][j] + 1 前提: h[i + 1][j] < h[i][j]
向后滑: f[i - 1][j] + 1 前提: h[i - 1][j] < h[i][j]

使用递归解决$DP$问题的前提是图是拓扑图，不会出现环，本题有前提因此不会出现环

核心算法

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//定义偏移量

int dp(int x, int y)
{
    int &v = f[x][y];//&v引用符号，每次写v都等同于写f[x][y]
    if(v != -1) return v; //v被算过，直接返回v，否则计算v
    
    v = 1; //最差v也可以走当前的格子
    for(int i = 0; i < 4; i ++)
    {
        int a = x + dx[i], b = y + dy[i];
        if(a >= 1 && a <= n && b >= 1 && b <= m && h[a][b] < h[x][y])
            v = max(v, dp(a, b) + 1);
    }

    return v;
}

int main()
{
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            cin >> h[i][j];

    memset(f, - 1, sizeof(f));//常用，表示每一个点都没有被算过

    int res = 0;
    for(int i = 1;i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            res = max(res, dp(i, j));

    cout << res << endl;

    return 0;
}

基础动态规划 | OI笔记

Shawn

基础动态规划

$Dynamic\ Programming$

背包问题：

经典背包问题特点

01背包

完全背包

朴素解：

一维优化：

多重背包

朴素版本：

多重背包的二进制优化 $O(w·n·logs)$：

分组背包

依赖背包

线性动态规划

1. Acwing895-最长上升子序列

暴力版本 $O(n^2)$

单调优化版：$O(n · logn)$

2. Acwing897-最长公共子序列

区间dp

计数类dp

完全背包解

其他解法

数位$DP$

情况分析

状态压缩$dp$

二进制操作

例1

核心代码

例2

暴力思路

状态压缩DP思路

树形$DP$

记忆化搜索

闫氏$DP$分析法

核心算法

Other Articles

深度优先搜索与广度优先搜索 | OI笔记

栈和队列 | OI笔记