壹 - 试题 算法提高 夺宝奇兵
线性动态规划模型——经典的"数字三角形"的翻版，因为状态转移过程十分清晰，十分适合作为入门之选。
题目描述
解题报告
注意最大数目，看到这个，潜意识想是不是要找最优解了?最优解？？，动态规划治的就是最优解！
记住这个一种线性DP的模型。它的背景是数字三角形，可能是大多数学动态规划的小伙伴的启蒙题目了吧。
观察这个三角形，对于每个点：
它是可以从左上方转移过来，也可以从右上方转移过来。
动态规划的本质了，说直白一点，不整高大上的概念，有点类似于一个递推的过程。
那么我们在划分状态的时候可以将，得到当前状态的最后一个不同点作为划分的依据。
因为是递推，下一个状态的时候，也是如此与考虑，那么整个过程就自底向上的将问题逐渐解决了。
闫式DP分析法：
1、状态表示
集合f[i,j]表示的是从顶点走到(i,j)这个点，其路径上的总和。
集合存的是一个数字，那么最终落实下来，这个数字就被称为集合的属性，这里存的是总和的最大值。
2、状态计算
状态计算是化整为零的过程，将已经划分的集合，处理为一些相似的状态，从而实现分而治之的效果。划分的依据就是上文说的最后一个不同点。
可能有小伙伴不太清楚，这个状态转移方程怎么就出来了呢？
因为，首先我们整体是一个归类的思想，所有从顶点走到图示中(4,2)这点的方案，算作一个集合。
也就是，无论是走的7->3->8->7还是的7->8->1->7，都是看做同一个类。
对这个类处理的时候，因为它们最后都肯定会走到(4,2)这个点。
这里就又出现了一个之后文章会反复提起的一句话：把全班分数整体减10分，第一名还是第一名，整体情况不受到影响，但是更加利于数据分析
同样，我们先将(4,2)剔除，就可以很清晰处理最后一个不同点——是从左上转移过来还是右上转移过的。处理好了，补加上这个必定经过的点
参考代码(C++版本)
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int N = 510,INF = 1e9; int a[N][N]; int f[N][N]; int n; int main() { scanf("%d",&n); //输入 for(int i = 1; i <= n;i++) for(int j = 1; j <= i;j++) cin >> a[i][j]; //初始化数组为负无穷，注意左边边界的空白和右边边界的空白也要初始化的 //比如(2,2)位置的8，因为是集合的思想，它也可能从右上转移过来 //但是那儿实际是没有数据的，因此处理为负无穷 for(int i = 1; i <= n+1;i++) for(int j = 0; j<=i+1;j++) f[i][j] = -INF; //开始DP f[1][1] = a[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]+a[i][j],f[i-1][j]+a[i][j]); //枚举最后一行，找到最大值 int res = -INF; for(int i = 1;i <= n;i++) res = max(res,f[n][i]); cout << res <<endl; return 0; }
贰 - 历届试题 数字三角形【第十一届】【省赛】【C组】
线性动归规划——数字三角形的进阶+掌握数论小知识
题目描述
解题报告
大概读完这个题，看到那种熟悉的图，可能小伙伴可能想说，怎么放了一个一模一样的题目
小伙伴们再细细品读这个可爱的题，它是有坑的…
相比于常规的数字三角形，它说：此外，向左下走的次数与向右下走的次数相差不能超过1。
因为自己也十分的菜，第一次看到这个限制的想法是自己用两个数记录向左走和向右走的。但是发现反而把自己绕糊涂了
正是因为这个小小的限制，反而也成就了这个题。
因为向左下走的次数与向右下走的次数相差不能超过1，那么整个路线从三角形的顶点开始，那么一路下来都是均匀的。
即：
当最后一层是偶数个数的时候，一定是落在最中间的两个数中的一个上；
当最后一层是奇数个数，一定是落在中中间的那一个位置上。
所以我们只需要按照数字三角形的常规思路走，最后依旧最后一行的情况，找到相应的数据，听起来其实有点哈希的思想在里面的，先预处理，最后用O ( 1 ) O(1)O(1)实现查找。
那么我就不重复的进行状态表示和状态计算的分析了，直接将DP分析图放上了。
参考代码(C++版本)
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 110,INF = 0x3f3f3f3f; int a[N][N]; int f[N][N]; int n; int main() { cin >> n; for(int i = 1; i <= n;i++) for(int j = 1; j <= i;j++) cin >> a[i][j]; //初始化 for(int i = 1; i <= n+1;i++) for(int j = 1; j <= i+1;j++) f[i][j] = -INF; f[1][1] = a[1][1]; //开始DP for(int i = 2;i <= n;i++) for(int j = 1; j <= i;j++) f[i][j] = max(f[i-1][j-1]+a[i][j] , f[i-1][j]+a[i][j]); int ans = 0; //输入最后一排的个数是偶数，那么中间两个选 if(n % 2 == 0) ans = max(f[n][n/2],f[n][n/2+1]); //最后一排是奇数，那么就输出中间位置上的数据 else ans = f[n][n/2+1]; cout << ans << endl; return 0; }
叁 - 历届真题 蓝肽子序列【第十一届】【决赛】【研究生组】
线性动态规划中的最长公共子序列模型 + 最大值这个属性是可以重复的
题目描述
解题报告
公共子序列的题，大多数是可以很明显的看到公共、公共长度等字眼
因为数据范围是1000嘛，可能有小伙伴想的，暴力一下？因为在公共子序列匹配的时候，当前这个位置可以相同，也可以不相同，那么就是2 1000 2^{1000}2
1000
次的运算，所以只能转而求其次，使用可以优化暴力的动态规划。
最长公共子序列的常规模型的分析方式
最长公共子序列的常规分析方式还是有点小小的模板的味道，顺着闫式DP分析的思路，系统的演示一下怎么获得状态转移方程~
假如有两个子序列，分别叫做a aa和b bb
状态表示：
集合：f[i][j]表示a的前i个字母，和b的前j个字母的最长公共子序列长度的集合
属性：最大值
状态计算：
状态计算对应的是集合划分的过程，划分的依据是当前能利用起来的最后一个不同点。
这里有个划分细节，是以前在y总的课中听到的，可以注意，心中有个底就好，现阶段不必纠结的，有个印象，能Ac比啥都好。
对于本题而言：可以依据a[i]和b[j]是否包含在当前的子序列中来划分。
情况一： a[i] 和 b[j]都不在，此时状态转移方程为f[i-1][j-1]
情况二： a[i]不在，b[j]在，此时状态转移方程可以写为：f[i-1][j]
这里了，看似是f[i−1][j] ,实际上无法用f[i−1][j]表示的。
因为f[i−1][j]表示的是在a aa的前i − 1 i-1i−1个字母中出现，并且在b bb的前j jj个字母中出现,此时b[j]不一定出现，这与条件不完全相等。
当前情况是a[i]一定不在子序列中，b[j]一定在子序列当中。
但仍可以用f[i−1][j]来表示，因为是当前情况是f[i-1][j]的一个子集，咱们要求的是max，不影响结果。
这就是我上文说的，在划分的时候，本来是要严格遵守不重不漏的原则，但是对于最大值而言，是可以重复的。
情况三：a[i]在，b[j]不在，此时状态转移方程可以写为：f[i][j-1]
情况四：a[i]和b[j]都在，此时状态转移方程为f[i-1][j-1] + 1
综上所述，可以得到这闫式DP分析图。
参考代码(C++版本)
#include <bits/stdc++.h> using namespace std; const int N = 1010; int f[N][N]; string s1, s2; string str1[N], str2[N]; int cnt1, cnt2; int main() { //输入 cin >> s1 >> s2; //获取两个字符串长度 int len1 = s1.length(), len2 = s2.length(); //分割蓝肽 for (int i = 0; i < len1;) { //遇到大写字母，就是遇到蓝肽了 if (s1[i] >= 'A' && s1[i] <= 'Z') { str1[++cnt1] += s1[i++]; while (s1[i] >= 'a' && s1[i] <= 'z') str1[cnt1] += s1[i++]; } } for (int i = 0; i < len2;) { if (s2[i] >= 'A' && s2[i] <= 'Z') { str2[++cnt2] += s2[i++]; while (s2[i] >= 'a' && s2[i] <= 'z') str2[cnt2] += s2[i++]; } } for (int i = 1; i <= cnt1; i++) for (int j = 1; j <= cnt2; j++) { if (str1[i] == str2[j]) f[i][j] = f[i - 1][j - 1] + 1; else f[i][j] = max(f[i][j - 1], f[i - 1][j]); } cout << f[cnt1][cnt2] << endl; return 0; }
肆 - 历届真题 砝码称重【第十二届】【省赛】【A/B/C组】
选择模型中的01背包的变型
题目描述
解题报告
看到题目中说到让咱们寻找一个最优解，那么这个时候，可以尝试向着动态规划的方向去思考。
本题是在有限制的情况下进行选择，也就是以背包问题为代表的选择模型。
系统温习背包问题：
背包问题中f [ i ] [ j ] f[i][j]f[i][j]表示从前i ii个物品中进行选择，在背包容量为j jj的背包中能够存放的物体价值之和的最大值。
对于本题：
状态表示：
集合：集合f[i][j]表示的含义是从前i个砝码中进行选择且总体积为j的所有方案的集合
属性：这个集合所存储的属性是集合是否非空。表示从前i个砝码中选出总重量为j的方案是否存在，可以很明显的看出，是一个bool值。
状态计算：
状态计算对应的是对咱们规定的集合的划分，划分的依据大多是最后一个不同点。
比如本题，最后一个不同点就是当前这个砝码是怎么进行放置：
假如要称重的物品默认放在左边
1、不选当前砝码，即 f[i][j] = f[i-1][j]
2、选择当前砝码来增加称重盘中的重量(即把当前砝码放在右边)，f[i][j] = f[i-1][j-w[i]]
3、选择当前砝码来削减称重盘中的重量(即把当前砝码放在和物品一起)，f[i][j] = f[i-1][j+w[i]]
将如上的步骤进行整理的，那么就可以得到这张闫式DP分析图
同样的，对应一定会选择的砝码i，依旧先采用先剖除它并不会影响整体格局的思想，也就是i-1，对应修改总和j受到的影响。
参考代码(C++版本)
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 110,M = 100010; int n,m; int w[N];//存储砝码质量的数组 bool f[N][2 * M];//表示状态的数组 int main() { cin >> n; //DP环节会有减一的，都建议从1开始获取值 for(int i = 1; i <= n;i++) cin >> w[i],m += w[i]; //初始化，这行代码的意思是，从前0个砝码中选出总和为0的方案是存在的 //M 只是都要加的一个偏移量 f[0][M] = true; //枚举n个砝码 for(int i =1; i <= n;i++) { //枚举会出现的重量，因为可能为负，所有统计加上了一个偏移量M for(int j = -m; j <= 2 * m ;j++) { //情况一：不选当前砝码的集合不是空 if(f[i-1][j+M]) { f[i][j+M] = true; continue; } if(j - w[i] >= -m &&f[i-1][j- w[i] + M]) { f[i][j+M] = true; continue; } if(j + w[i] <= m && f[i-1][j+w[i] + M]) { f[i][j+M] = true; } } } //遍历得到的方案，统计结果 unsigned long long cnt = 0;//unsigned可用于防止溢出 for(int i = 1; i <= m;i++) if(f[n][i+M]) cnt ++; cout << cnt << endl; return 0; }
伍 - 历届真题 包子凑数【第八届】【省赛】【A/B组】
选择模型中的完全背包+掌握数论互质判断(gcd)
题目描述
解题报告
通俗来说了，就是包子大叔有很多笼固定数量的包子，比如5个一笼的，9个一笼的。
有无限笼，注意无限这两个字，然后细细品读这句话小明想知道一共有多少种数目是包子大叔凑不出来的。
这句话的意思就是让咱们找到最优解，那么动态规划可以拿出来了，看到无限二字，向着完全背包的方向思考。
对于常规情况下，完全背包状态转移方程通式的获得是经过如下的闫式分析以及数学归纳之后的结果，我只是放置在这儿，不去证明了。
根据小伙伴们的需求，能理解性的记忆最好。假如时间吃紧的话也可以直接背下来先用着，以后再回头理解它的时候回会很轻松的.
本题需要注意的第二个点是一个数学规律：
当两个整数p、q互质时，最大不能组成的整数为 (p-1)(q-1) – 1 ；
当两个整数不互质时，不存在最大不能组成的整数，即最大不能组成的整数为无穷大。
整数间若不互质，最大公因子为d，即每个整数都是d的倍数。
d > 1时，最大不能组成的整数为无穷大。因此，可以先计算出n个整数的最大公因子，若 > 1，则输出INF。
若等于1，则采用动态规划进行分析
状态表示：
集合：集合f[i,j]表示前i个数值的蒸笼凑成的包子数目为j的方案的集合
属性：Bool 也就是说存储的是集合是否为空
状态计算：
依旧是依据最后一个不同点，完全背包中，最后一个不同点就是当前这个物品i选择的数量。可以选0个，也可以选k个。
①、不选当前这笼包子就可以凑出j： f[i-1,j]
②、当前这笼包子要选k个就可以凑出j：f[i-1,j k * v[i]]
因为对于本题的包子而言，就只有探讨数量的，所以对比传统的完全背包，少了一个w[i]
参考代码(C++版本)
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 110, M = 10010;//M 是 最多一百种蒸笼，每笼包子最多100个 int v[N]; bool f[N][M]; int n; //判断最大公约数，即欧几里得算法 int gcd(int a,int b) { return b? gcd(b,a % b) : a; } int main() { //处理输入 cin >> n; for(int i =1; i <= n;i++) cin >> v[i]; //根据本题的数学背景。现在要去找到读入的数据的最大公约数 int x = v[1]; for(int i = 2; i <= n;i++) x = gcd(x, v[i]); //判断最大公约数是否大于1 if(x > 1) printf("INF\n"); //最大公约数为1，也就说，它们是互质的，那么开始DP else { //初始化 f[0][0] = true; for(int i = 1; i <= n;i++) for(int j = 0; j <= M;j++) { if(f[i-1][j]) { f[i][j] =true; continue; } int k = 1; while(j - k * v[i] >= 0) { if(f[i-1][j-k*v[i]]) { f[i][j] = true; break; } //跳出当前的选择，进行一下个 k++; } } long long cnt = 0; //遍历所有组合，输出答案 for(int i = 1; i <= M;i++) if(f[n][i] == false) cnt++; cout << cnt <<endl; } return 0; }
陆 - 历届真题 调手表【第九届】【决赛】【B组】
一、记录是因为防止思维定势，闫式DP分析是帮助分析，不是说一定要画它。
二、它是有点类似于完全背包，但是和完全背包还是有点区别，比完全背包更单纯
题目描述
解题报告
一、意识培养
当看到找最优解，而且给的信息是可以无限用的，然后让咱们找到凑出某个数值的方案的时候，就可以向着完全背包的方向思考，比较让人安心的是，这个题感觉是伪完全背包，只是用到其中的一点点思想
二、温习完全背包
完全背包最淳朴的版本是这种的：
对其进行状态表示和状态计算的分析：
状态表示：
集合：f[i][j]表示从i个物品进行选择，总体积不超过j的方案的集合
属性：属性大多数是最大值max
状态计算：
状态计算对应的是对咱们所定义的集合f[i][j]的划分过程，划分依据是最后一个不同点。
对于完全背包而言，最后一个不同点就是当前这物品，它被用了多少次才凑出这个总体积j jj的。
小伙们也可以看这张出上述步骤总结出来的闫式DP分析图，稍显凌乱了
三、降服本题
这道题中，+1和+k kk是可以无限用的，对比起标准完全背包，它只有两个物品在无限用，标准完全背包的状态转移方程就不适用了，这会困扰咱们吗？不，这让题变得更简单了。
闫式DP分析
状态表示：
集合：f[i]表示从0分钟调整到i分钟，需要调整多少次
属性：最小值
状态计算：
要么从+1转移过来，要么从+k转移过来，那么还原回到(i-1)的状态的时候，只需要扣除相应的值，同时补上这次调整，也就是+1。
写到这儿，我感觉它又像01背包了，这个题蛮可爱的。
[i] = min(min(f[(i-1)%n], f[(i+n-k)%n]), f[i])+1;
最后遍历得到的方案，得到答案。
参考代码(C++版本)
#include <iostream> #include <algorithm> #include <cstdio> using namespace std; long long n, k, j; int f[100010]; int main() { cin >> n >> k; //初始化，默认一次是一分钟，那么现在是多少次，就是多少分钟 for(int i = 0; i < n; i++) f[i] = i; //进行一步预处理，找到每个时间点，一次走k下，所有需要的最少次数 for(int i = 1; i < n; i++) { j = i*k % n; f[j] = min(f[j], i); } //因为f[0]不用处理了，从2开始枚举 for(int i = 2; i < n; i++) f[i] = min(min(f[(i-1)%n], f[(i+n-k)%n]), f[i])+1; int maxv = 0; for(int i = 1; i < n; i++) maxv = max(maxv, f[i]); cout << maxv << endl; return 0; }
关于动态规划的一点建议
大致浏览完这篇文章的小伙伴可以发现，这篇文章几乎没有什么概念，定义和晦涩的知识点了，全是实打实的硬仗。
因为动态规划不像最短路、或者搜索会有板子可以背，学它的最好建议是在闫式DP分析的帮助下，再去试着刷，然后就会感觉看到一些题就知道，可以用动态规划，甚至可以有直接秒出状态转移方程的感觉的，大家要相信自己呀。
