AcWing算法基础课笔记 ------ 第五章 动态规划
发布时间
阅读量：
阅读量
文章目录
-
一. 线性dp
-
- 1. 数字三角形
- 2. 最长上升子序列
- 3. 最长公共子序列
-
二. 区间dp
-
- 1. 石子合并
-
三. 计数类dp
-
- 1. 整数划分
-
四. 状态压缩dp
-
- 1. 蒙德里安的梦想
- 2. 最短Hamilton路径
-
五. 树形dp
-
- 1. 没有上司的舞会
-
六. 记忆化搜索
-
- 1. 滑雪
这篇笔记是对动态规划知识进行系统学习和总结的文章，在这些内容中涉及的计数类dp 部分较为复杂且难以掌握，在深入理解之前没有继续扩展。
一. 线性dp
其核心在于通过连续或逐层的方式计算每一个状态变量f[i]或f[i][j]的具体值。这种按照顺序进行状态转移的方式体现了问题具有的线性特征,因此我们将其归类为线性动态规划（linear dynamic programming）。
1. 数字三角形
这道题要求我们选择一条从顶端到底端的路径，并使经过的路径之和达到最大值。遇到这类动态规划问题时，我们应该首先进行如下分析：
- 状态描述：
- 集合定义：f[i][j] 表示所有从起点到坐标(i,j)的路径。
- 属性定义：对于每一条路径计算其最大值。
- 状态计算：
- 要达到该坐标(i,j), 只能从其左上方和右上方的相邻点转移而来。
- 所以可以得出状态计算的方程是:
f[i][j] = max(f[i - 1][j - 1] + g[i][j], f[i - 1][j] + g[i][j])
通过前述的这些步骤进行编码实现会相对简便
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510, INF = 1e9;
int n;
int g[N][N],f[N][N];
int main()
{
scanf("%d",&n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
scanf("%d",&g[i][j]);
//Init
for (int i = 0; i <= n; i++)
for (int j = 0; j <= i + 1; j++)
f[i][j] = -INF;
f[1][1] = g[1][1];
for (int i = 2; i <= n; i++)
for (int j = 1; j <= i; j++)
f[i][j] = max(f[i - 1][j - 1] + g[i][j], f[i - 1][j] + g[i][j]);
int res = -INF;
for (int i = 1; i <= n; i++)
res = max(res,f[n][i]);
printf("%d\n",res);
return 0;
}2. 最长上升子序列
这道题要求我们找出一个数组中的序列，并且这个序列必须保持递增顺序；虽然不一定需要这些元素是连续的排列在一起的元素点位之间也不必存在直接连接的关系；我们的目标是要寻找最长这样的序列。我们仍然先来分析这个问题：
- 状态表示：
- 集合：
f[i]表示第i个数的 全部 递增子序列的长度。 - 属性：对于每一个可能的递增子序列长度 进行取 最大值。
- 状态计算:
- 对于图中的每个j来说, 它会从起始点开始, 直到位置 j - 1为止, 如果发现nums[j] < nums[i], 那么我们就会比较f[i] 和 f[j] + 1中的较大者.
- 因此在其计算过程中, 需要从位置1 到 i - 1之间的这个区间内进行遍历.
- 状态计算方程：
f[i] = max(f[i] , f[j] + 1)
代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n;
int nums[N],f[N];
int main()
{
scanf("%d",&n);
for (int i = 1; i <= n; i++)
scanf("%d",&nums[i]);
for (int i = 1; i <= n; i++)
{
f[i] = 1; //对于第i个数本身永远都会有1的长度
for (int j = 1; j < i; j++)
if(nums[j] < nums[i])
f[i] = max(f[i],f[j] + 1);
}
int res = 0;
for (int i = 1; i <= n; i++)
res = max(res,f[i]);
printf("%d\n",res);
return 0;
}3. 最长公共子序列
首先对这个问题进行动态规划方法（DP）求解：
- 状态表示：
- 集合：其中
f[i][j]代表字符串a的前i个字符与字符串b的前j个字符之间的所有公共子序列的情况。 - 属性：这些子序列中选取最长的一个作为属性。
- 状态计算:
- 在状态计算方面：当我们比较两个字符串中的相应字符时，
- 集合：其中
实际上，在这种情况下（即第一种都不选的情况），无论是否进行判断都无所谓。因为中间两种情况已经涵盖了这种情况（即它们已经包含了这种情况）。因此无需对这种情况再执行max操作。
代码如下：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,m;
char a[N],b[N];
int f[N][N];
int main()
{
scanf("%d%d",&n,&m);
scanf("%s%s",a + 1, b + 1);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if(a[i] == b[j])
f[i][j] = max(f[i][j],f[i - 1][j - 1] + 1);
}
printf("%d\n",f[n][m]);
return 0;
}二. 区间dp
上面的线性dp主要体现在处理f数组的过程中，在这一过程中会延续之前计算的结果一层一层地进行求解而被称作线性结构相比之下区间dp则是在划分两个子区间的基础上通过逐步合并计算来完成整个区间的运算
1. 石子合并
- 状态表示：
- 数据结构
f[i][j]定义了第 i 堆至第 j 堆合并后的总代价。 - 特性：该模型对每一步操作的总代价取最小值。
- 状态计算：
- 观察到 k 在 left 位置开始连续枚举至 right-1 的位置。
- 计算过程遍历所有可能的合并组合后找到最小值的结果即为24。
- 所以可以得出状态计算的方程为：
f[l][r] = min(f[l][r], f[l][k]) + f[k + 1][r] + s[r] - s[l - 1]
我们之前在讨论中直接采用了f[1,2]这一指标的最小代价计算方法，在探讨其背后的原理时发现一个问题：f[1,2]本身的代价是如何得出的呢？具体来说，在计算过程中我们观察到当计算范围从"12"（即长度为2）逐步扩展至"13"（长度为3）以及"1~4"（长度为4）时会发现一些规律性的东西。由此可以推断出该算法是以不同长度区间为基础进行计算的
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 310;
int n;
int s[N],f[N][N];
int main()
{
scanf("%d",&n);
for (int i = 1; i <= n; i++)
scanf("%d",&s[i]);
for (int i = 1; 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] = 1e8;
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]);
}
}
printf("%d\n",f[1][n]);
return 0;
}三. 计数类dp
1. 整数划分
该题目可建模为一个完全背包问题，在此过程中需要特别注意其与普通背包问题的区别在于集合属性方面的差异较大。
完全背包问题即为：在i个物品中选取若干使得总体积不超过j的所有组合方案中价值的最大值。
而正向划分则是在考虑所有可能的组合时，在达到体积j的所有方案中的数量。
- 状态变量
- 集合：其中
f[i][j]代表从前i个物品中选择体积恰好为j的所有方案数 - 属性：求取所有方案的和
- 状态计算：
动态规划的状态转移方程如下所示
- 集合：其中
把这个问题转化成完全背包问题，1~n 是物品的体积v也是价值v
然后像完全背包问题那也那样子优化一下
f[i][j] = f[i - 1][j] + f[i - 1][j - i] + f[i - 1][j - 2i] + ... +f[i - 1][j - si];
f[i][j - i] = f[i - 1][j - i] + f[i - 1][j - i - i]+...+f[i - 1][j - si];
f[i][j] = f[i - 1][j] + f[i][j - i];
对其进行一维数组的优化：
f[j] = f[j] + f[j - i]二维：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010, mod = 1e9+7;
int n;
int f[N][N];
int main()
{
scanf("%d",&n);
//前i个物品容量为0的时候也就是不需要选的，也算是一种方案
//最开始都不选的方案数是1
for (int i = 0; i <= n; i++)
f[i][0] = 1;
for (int i = 1; i <= n; i++)
for (int j = 0; j <= n; j++)
{
f[i][j] = f[i - 1][j];
if(j >= i)
f[i][j] = (f[i - 1][j] + f[i][j - i]) % mod ;
}
printf("%d\n",f[n][n]);
return 0;
}一维：
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010, mod = 1e9+7;
int n;
int f[N];
int main()
{
scanf("%d",&n);
//前i个物品容量为0的时候也就是不需要选的，也算是一种方案
//最开始都不选的方案数是1
// for (int i = 0; i <= n; i++)
// f[i][0] = 1;
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 ;
}
printf("%d\n",f[n]);
return 0;
}四. 状态压缩dp
当碰到状态压缩型动态规划时, 我怀着满腔好奇翻开这一章节, 结果令我意想不到, 感觉自己瞬间"懵逼大法", 陷入学习困境.这类dp方式通常会将问题的状态转换为二进制位的形式, 每个二进制位代表一种状态, 通过整数或位运算来计算各状态间的转移关系.
下面这两道题，一天 ，真就一天的时间才搞懂。
1. 蒙德里安的梦想
题目要求我们将给定的 N*M的棋盘切割，其实也可以当成填充去做。
- 状态定义：
- 集合部分：f[i][j]定义为在前i-1列已完全摆放完毕，并且第i列延伸至j的所有方案数。
- 属性方面：我们需要统计所有可能的方案数量。
- 状态计算：
- y总的方法仅考虑合法放置的行（每行占据1×2空间）。一旦所有行都放置完毕后，列将没有剩余位置可选，因此只需统计所有合法排列方式的数量。
- 我们已经明确了f[i][j]的具体含义。其中j是一个整数变量，在实际操作中被转换为二进制形式处理。例如，在二进制中j=1001时，则表示左侧有溢出的情况。
- 如何计算上图中
f[i][j]自身的方案数？当处理到i时，实际上f[i - 1][]已经确定完毕并得到了结果。- 因此我们需要引入一个变量k来遍历上一列的所有可能情况。在此过程中我们还需判断合法这一关键条件。
- 首先(j & k) == 0通过观察图形可知j与k之间不存在交点这意味着这种组合是不被允许的。
- 其次 st[j | k] 必须是合法的，st[i | j]：这个表达式是在判断新状态 i | j 是否是合法状态，即是否可以放置连续的偶数个方块。st 数组中存储了每个状态是否为合法状态的信息。
- 然后将所有合法 的k 全部加起来就好了
f[i][j] += f[i - 1][k]
我们首先得预处理出所有的情况 就是 0 ~ 2^n 种
下面是代码：
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 12, M = 1 << N;
int n,m;
LL f[N][M];
bool st[M];
int main()
{
while(cin >> n >> m, n || m)
{
//
for (int i = 0; i < 1 << n; i++)
{
int cnt = 0;
bool is_valid = true;
for (int j = 0; j < n; j++)
{
if (i >> j & 1) //碰上1
{
if(cnt & 1) //判断连续的空位置是否是偶数
{
is_valid = false;
break;
}
}
else
cnt++;
}
//最后一段
if (cnt & 1) is_valid = false;
st[i] = is_valid;
}
memset(f,0,sizeof f);
f[0][0] = 1; //空棋盘有一种方案
//按照列去放，所以是 <= m; f[m][0] 则可以表示前 m - 列已经放好，并且伸到m列的状态是0，也就是没有的方案总数。
for (int i = 1; i <= m; i++)
for (int j = 0; j < 1 << n; j++)
for (int k = 0; k < 1 << n; k++)
if ((j & k) == 0 && st[j | k])
f[i][j] += f[i - 1][k];
printf("%lld\n",f[m][0]);
}
return 0;
}上面的代码还可以且进行优化, 将dp循环中的if条件提取出来, 不用每次都且进行判断, 只需判断一次, 将合法j对应的合法k放入二维数组中即可.
f[i][j] = f[i - 1][state[j][k]]
代码如下：
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int N = 12, M = 1 << N;
typedef long long LL;
int n, m;
LL f[N][M];
bool st[M];
vector<int> state[M];
int main()
{
while (cin >> n >> m, n || m)
{
//首先预处理处所有的格子伸展情况有哪些可以正好存放竖着的1*2小方格
for (int i = 0; i < 1 << n; i++)
{
int cnt = 0;
bool is_valid = true;
for (int j = 0; j < n; j++)
{
if (i >> j & 1) //遇到1
{
if (cnt & 1) //遇到1时候连续空格子是奇数，就意味着肯定无法摆满。
{
is_valid = false;
break;
}
cnt = 0;
}
else //积累0的次数
cnt++;
}
//最后一段
if (cnt & 1) is_valid = false;
st[i] = is_valid;
}
//预处理所有的组合.
//每个数i 可以有多少个与其成功组成的数j.
for (int i = 0; i < 1 << n; i++)
{
state[i].clear();
for (int j = 0; j < 1 << n; j++)
if ((i & j) == 0 && st[i | j]) //不冲突，并且正好能填满剩余的小方块。
state[i].push_back(j);
}
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 : state[j])
f[i][j] += f[i - 1][k];
cout << f[m][0] << endl;
}
return 0;
}2. 最短Hamilton路径
这道题目同样采用了二进制数字来表示状态。与前一个问题不同，在这里我们是如何标识哪些顶点被访问过或未被访问。
-
状态表示：
-
集合：
其中集合中的元素由变量 f[i][j] 定义：变量 i 表示已访问的顶点集合（以二进制形式），而变量 j 表示当前所在的顶点。
变量 i(二进制)的状态代表已能访问的所有顶点集合，在此状态下到顶点 $j$ 的最短路径长度即为f[i][j]` -
属性项：对所有路径求最小值。
- 状态计算过程：
- 首先需要明确该状态压缩机制中二进制是如何进行压缩的。
比如： 0 -> 1 -> 2 -> 4
可以用二进制： 10111来表示
此二进制下的前三位对应着012顶点，第5位对应着4顶点。
1则表示这些顶点被用过了。随后我们对所有二进制状态进行遍历，在最终的状态中即为f[(1 << n)][n - 1]表示所有顶点都被访问过，并且此时位于n-1号顶点上。这正是我们所寻求的结果。
随后我们在遍历过程中会对所有的顶点距离进行重新计算，在这一过程中会引入一个变量k来进行迭代运算。
例如，在处理到第j个顶点时，则会考虑所有可能的情况中的第k个中间节点来进行距离更新。
换句话说，在当前的状态i中去除掉第j号节点后，并通过第k号节点再次到达第j号节点。
而f[i][j]则被赋值为min(f[i][j], f[i - (1 << j)][k] + w[k][j])。
代码如下：
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 20, M = 1 << N;
int n;
int f[M][N],w[N][N];
int main()
{
scanf("%d",&n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d",&w[i][j]);
memset(f, 0x3f, sizeof f);
f[1][0] = 0; //f[0....01][0]第一个顶点的状态，在0的位置，也就是起点到起点的距离是0
for (int i = 0; i < 1 << n; i++)
for (int j = 0; j < n; j++)
if(i >> j & 1) //当前的顶点合法是1，也就是说当前的顶点状态。
{
for (int k = 0; k < n; k++)
if(i - (1 << j) >> k & 1) //当前的状态先除掉j,之后经过k之后的距离 和 直接到j的距离取最小值
f[i][j] = min(f[i][j],f[i - (1 << j)][k] + w[k][j]);
}
printf("%d\n",f[(1 << n) - 1][n - 1]);
return 0;
}五. 树形dp
在树结构中执行动态规划的过程被称为树形动态规划。
由于处理树结构通常会采用递归的方式进行操作。
因此，在解决大多数与之相关的问题时，递归方法是常用的策略。
1. 没有上司的舞会
- 状态表示：
- 集合：f[u][0]代表以u为根节点且不选择u时的所有快乐指数方案；f[u][1]代表以u为根节点并选择u时的所有快乐指数方案。
- 属性：对这两种方案取最大值。
- 状态计算:
- 根据题意可知，在树结构中不存在一个节点是另一个节点的直接父节点。
- 因此对于每个单独的根节点而言，在集合定义的基础上都存在两种状态的选择：选中该根节点或者未被选中。
- 当未被选中的情况下，则允许其子节点进行相应的状态选择；当选中该根节点时，则其子节点均无法被选择。
- 基此我们可以得到两个递推关系式：
- 设s为u的一个孩子；i则表示第i个子孩子。
- 当未被选中该根结点时：f[u][0] += max{f[s_i][0], f[s_i][1]}；这是因为未选择当前结点的情况下其子结点的状态选取具有独立性。
- 而当选中该根结点时：f[u][1] += f[s_i][0]；因为当选中当前结点后则所有子结点均无法被选取。
代码如下:
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 6010;
int n;
int hahppy[N],f[N][2];
int h[N],e[N],ne[N],idx;
bool hasFather[N];
void Add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u)
{
f[u][1] = hahppy[u];
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
dfs(j);
f[u][0] += max(f[j][0],f[j][1]);
f[u][1] += f[j][0];
}
}
int main()
{
scanf("%d",&n);
for (int i = 1; i <= n; i++)
scanf("%d",&hahppy[i]);
memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; i++)
{
int a,b;
scanf("%d%d",&a,&b);
hasFather[a] = true;
Add(b,a);
}
int root = 1;
while (hasFather[root])
root++;
dfs(root);
printf("%d\n",max(f[root][0],f[root][1]));
return 0;
}六. 记忆化搜索
记忆化搜索技术是一种通过存储已经遍历过的状态信息以减小重复计算的工作方式，在确保每个状态只计算一次的同时采用递归方法进行操作。这其实也是一种属于搜索范畴的方法，在学习广度优先搜索（BFS）和深度优先搜索（DFS）时就接触过类似的问题处理方法。
1. 滑雪
- 状态定义:
- 数据结构:
f[i][j]用于表示顶点(i,j)的所有可能的解决方案的数量。 - 属性描述: 对于每一个顶点
f[i][j]的状态进行最大值优化处理。 - 状态计算:
- 计算过程: 这个过程类似于深度优先搜索算法, 从当前顶点出发向四周扩展四个方向进行探索。
- 条件判断: 在计算
f[i][j]的状态值时, 如果该位置已经存在有效的解, 直接采用已有的最优解。 - 最优策略: 在动态更新过程中, 每次计算都采用当前最优解, 并通过比较上下左右四个方向的最大值来确定下一步的最佳路径。
- 结果获取: 完成所有顶点的状态计算后, 对整个矩阵中的
f[i][j]值进行全局比较, 找出最大的那个作为最终结果。
- 数据结构:
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 310;
int n,m;
int g[N][N];
int f[N][N];
int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
int dp(int x, int y)
{
int &v = f[x][y];
//此状态已经计算出了
if(v != -1) return v;
v = 1;
for (int i = 0; i < 4; i++)
{
int a = x + dx[i], b = y + dy[i];
if (a >= 0 && a < n && b >= 0 && b < m && g[x][y] < g[a][b])
v = max(v,dp(a,b) + 1);
}
return v;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
scanf("%d",&g[i][j]);
int res = 0;
memset(f, -1, sizeof f);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
res = max(res,dp(i,j));
printf("%d\n",res);
return 0;
}全部评论 (0)
还没有任何评论哟~