学习笔记1:DP1-算法核心

天行健君子以自强不息。 ——《周易》日期2026.7.4 Saturday时间:19时学习内容DP算法C目录一、DP算法的概念及思想二、DP所具有的特点三、DP算法的解题步骤四、例题五、小结一、DP算法的概念及思想DP算法就是把一个大问题分解为若干个相对简单的小问题把每个问题用状态描述出了并按某个顺序依次求出每个状态的值。二、DP所具有的特点1、状态空间组成一个DAG有序无环图将DP算法的状态空间绘制成图其总是形成一个有序无环图。DP算法的状态空间不会形成环。2、图的节点对应“状态”有向边对应“转移”3、DP算法的遍历顺序为拓扑序。拓扑序定义如下对一个有向无环图 ( Directed Acyclic Graph 简称 DAG ) G 进行拓扑排序是将 G中所有顶点排成一个线性序列使得图中任意一对顶点 u 和 v 若边 u , v ∈ E ( G )则 u 在线性序列中出现在 v之前。通常这样的线性序列称为满足拓扑次序 ( Topological Order )的序列简称拓扑序列。简单的说由某个集合上的一个偏序得到该集合上的一个全序这个操作称之为拓扑排序。 ——百度百科如定义所示拓扑序是针对于DAG的一项定义这也是DP的状态空间不会形成环的原因。为什么DP算法的遍历顺序为拓扑序由DP算法的状态为节点构造的DAG其拓扑序列为这个DAG的所有顶点的线性序列满足“若有有向边u,v则在拓扑序列中u在v之前”。而由于在DP算法中DP的状态转移方程通常形式为 dp[v]f(dp[u])其中 u 是 v 的前驱节点。只有当所有前驱节点 u 的 dp 值确定后dp[v] 才能被正确计算所以u的遍历顺序应该在v之前即DP算法的遍历顺序是拓扑序。三、DP算法的解题步骤一般为以下几个步骤1、划分阶段。2、状态表示。3、决策与状态转移方程。4、确定边界条件。5、确定答案。这几个步骤是解题时必不可少的。一般代码模板#includebits/stdc.h using namespace std; const unsigned long long maxn1e55; int f[maxn];//定义DP数组 int main(){ // memset(f,初始值,sizeof(f));//初始化 f[开始位置]初始值;//边界条件 for(){ for(决策){ //转移方程 } } for(){ ansmax(ans,f[i]);//计算答案 } coutans;//输出答案 return 0; }常用初始值0x3f(正无穷)求最小值-0x3f(负无穷)求最大值0求方案数四、例题T1 文字工作【LUOGU B3636】题目描述机器猫要在电脑前打字。一共需要打 n 个字但现在文档里只有一个字。机器猫有两种操作可以做。假设现在已经有 x 个字机器猫可以选择往文档最后加一个字。字数变成 x1。把文档复制粘贴一遍。字数变成 2x。问机器猫至少需要多少次操作才能得到恰好 n 个字。输入格式仅一行一个正整数 n。输出格式仅一行一个正整数表示最少操作次数。输入输出样例输入#116 输出#14输入#25 输出#23数据规模与约定对于 100%的数据n≤106。解析设表示将文档中的字数改为字时的最少操作次数易得至于边界条件我们知道当时即。代码如下#includebits/stdc.h #define lll long long using namespace std; const unsigned lll N1e65; int n; int f[N]; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cinn; f[1]0; for(int i2;in;i){ f[i]f[i-1]1; if(i%20) f[i]min(f[i],f[i/2]1); } coutf[n]; return 0; }思考若将n的数据范围改为,这道题该怎么做实际上我们可以把这道题中的数字看成二进制来思考。不难发现题中的2x操作其实可以视为x左移2位。题目要求求出由1到n的最少操作次数也就是将1变为n需要进行多少次左移和1。要想知道左移和1的次数我们需要分别统计n的二进制的位数和其中1的个数再进行求和就是最终答案。我们可以使用函数log2()和__builtin_popcount()来分别计算它们。代码如下anslog2(n)__builtin_popcount(n); coutans;当然也可以进行手动实现。T2 [SHOI2002] 滑雪题目描述Michael 喜欢滑雪。这并不奇怪因为滑雪的确很刺激。可是为了获得速度滑的区域必须向下倾斜而且当你滑到坡底你不得不再次走上坡或者等待升降机来载你。Michael 想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子1 2 3 4 516 17 18 19 615 24 25 20 714 23 22 21 813 12 11 10 9一个人可以从某个点滑向上下左右相邻四个点之一当且仅当高度会减小。在上面的例子中一条可行的滑坡为24−17−16−1从 24 开始在 1 结束。当然 252423…321 更长。事实上这是最长的一条。输入格式输入的第一行为表示区域的二维数组的行数 R 和列数 C。下面是 R 行每行有 C 个数代表高度(两个数字之间用 1 个空格间隔)。输出格式输出区域中最长滑坡的长度。提示对于 100% 的数据1≤R,C≤100。输入样例5 5 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9输出样例25解析读完题目我们思考dp数组的定义这里我们将它这样定义f[i][j]表示以第i,j个元素结尾的最长斜坡其初始状态为全1。然而这样定义dp数组我们发现若以f[i][j]?的常规写法其转移方程异常难写。所以这里我们引入对转移方程的新写法——动态转移即我们的转移方程不去以上一步计算这一步而是以这一步去计算下一步。以这道题为例它的转移方程这样写答案就是还有只计算一遍数组是不行的会少算路径因此最外层也要套循环。时间复杂度O(R^2*C^2)而1R,C100,理论上没有问题。下面为代码#include bits/stdc.h using namespace std; using LL long long; using ULL unsigned long long; const int maxn 105; const LL inf0x3f3f3f3f; int R,C,ans-inf; int a[maxn][maxn]; int f[maxn][maxn]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cinRC; for(int i1;iR;i){ for(int j1;jC;j){ cina[i][j]; } } for(int i1;iR;i){ for(int j1;jC;j){ f[i][j]1; } } for(int y1;yR*C;y){ for(int i1;iR;i){ for(int j1;jC;j){ if(i1Ra[i][j]a[i1][j]){ f[i1][j]max(f[i1][j],f[i][j]1); } if(j1Ca[i][j]a[i][j1]){ f[i][j1]max(f[i][j1],f[i][j]1); } if(i-11a[i][j]a[i-1][j]){ f[i-1][j]max(f[i-1][j],f[i][j]1); } if(j-11a[i][j]a[i][j-1]){ f[i][j-1]max(f[i][j-1],f[i][j]1); } } } } for(int i1;iR;i){ for(int j1;jC;j){ ansmax(ans,f[i][j]); } } coutans; return 0; }然而感觉时间复杂度实在太高了思考有没有更NB的方法。记忆化搜索从一个格子只能滑向高度更低的相邻格子因此路径上的高度严格递减。这说明1不可能出现环因为高度一直变小。2对于每个格子可以定义一个状态f[x][y] 表示从 (x, y) 出发能够滑出的最长路径长度。3如果相邻格子 (nx, ny) 的高度小于当前格子 (x, y)那么可以转移f[x][y]max(f[x][y],f[nx][ny]1)由于同一个格子的答案可能被多次访问所以使用记忆化搜索避免重复计算。对于每一个格子都尝试把它作为滑雪的起点。用dfs计算从它出发的最长路径。代码如下#include bits/stdc.h using namespace std; int r, c, h[105][105], f[105][105]; int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; int dfs(int x, int y) { if (f[x][y]) return f[x][y]; f[x][y] 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 h[nx][ny] h[x][y]) { f[x][y] max(f[x][y], dfs(nx, ny) 1); } } return f[x][y]; } int main() { cin r c; for (int i 1; i r; i) for (int j 1; j c; j) cin h[i][j]; int ans 0; for (int i 1; i r; i) for (int j 1; j c; j) ans max(ans, dfs(i, j)); cout ans endl; return 0; }五、小结本篇介绍了DP算法的定义、思想、特点以及解相关题目的一般步骤。还有主动转移、记忆化搜索等对于dp算法的改进方式都进行了详细讲解。