目录
1、闫式DP分析法
2、背包问题
2.1 01背包问题
朴素版本
优化版本
2.2 完全背包问题
朴素版本
优化版本
2.3 多重背包问题
朴素版本
二进制优化
2.4 分组背包问题
3、线性DP
3.1 数字三角形
3.2 最长上升子序列
3.3 最长公共子序列
4、区间DP
5、数位统计DP
6、状态压缩DP
6.1 蒙德里安的梦想
朴素写法
去除无效状态的优化写法
1、闫式DP分析法
闫式DP分析法是从集合的角度分析DP问题。DP问题实际上就是求有限集中的最值、数量、是否存在等问题,而有限集中的元素通常是非常多的,此时就可以使用DP来进行优化。
DP问题的分析分为两个阶段。
状态表示
第一个阶段是状态表示,这是一个化零为整的过程,每次处理问题时,不是一个元素一个元素处理,而是每次都枚举一个子集(一类东西)。就是把一些有相似点的元素,化称一个子集,然后用某一状态表示。
状态表示要从两个角度分析:集合和属性
首先,要搞清楚状态表示的f[i]表示的集合是什么。对于集合的描述通常是所有满足...条件/方案的集合。正因为f[i]表示的是集合,是一类东西,不是一个东西,所以可以优化时间复杂度。其次,f[i]表示的是一个集合,但f[i]是一个数。存的这个数与集合的关系称为属性。属性一般是最大值/最小值/数量。
状态计算
第二阶段是状态计算,这是一个化整为零的过程。如何求出f[i]?需要将f[i]表示的集合划分成若干子集,每个子集单独去求。划分子集时每个子集要求做到不重、不漏。当然,不漏是一定要有的,但是不重就不一定,如求数量时要不重,而求最值时可以重复。求f[i]时,就分别求每一个子集的f[i],最后综合每一个子集的f[i],就是结果。划分集合的依据时:寻找最后一个不同点。
2、背包问题
2.1 01背包问题
2. 01背包问题 - AcWing题库
01背包问题就是每件物品只能选0次或1次
朴素版本
01背包问题是一个有限集中求最值的问题,因为物品数量、背包容量都是有限的,这也就限制了方案数是有限的,方案数是2^N个。问题就是从2^N个方案中选择一个符合题意的解法。若是暴力解法,就是枚举所有方案,时间复杂度是O(2^N)。而使用DP就可以优化时间复杂度
状态表示
背包问题本质是一个选择问题,选择问题的状态表示都是很类似的。第一维是只考虑前i个物品,后几维一般是题目的限制。在这道题中状态表示可以使用f(i, j)。f(i, j)表示的集合是所有只考虑前i个物品,且总体积不超过j的选法的集合。f(i, j)的属性是集合中所有方案的价值的最大值。当f(i, j)全算完后,答案就是f(N, V)
状态计算
状态计算时我们需要划分f(i, j)表示的集合。划分的依据是找最后一个不同点。在这道题中,选最后一个物品的方法,有选和不选两种,所以将集合划分为所有不选第i个物品的方案和所有选择第i个物品的方案这两个子集。每个子集要么选了第i个物品,要么没选。所以是不重不漏的。f(i, j)的取值就是取左边和右边值较大的哪一个。
现在来看如何求出左右两个子集的最大值。左边的集合表示的是所有不选第i个物品的方案的集合,很明显就是f(i - 1, j)。右边的集合表示的是所有选择第i个物品的方案的集合,若我们固定选择第i个物品,我们可以将选法分成变与不变两个集合,不变的是第i个物品组成的集合,因为每次都会选择,变的是前i - 1个物品,且总体积不超过j - vi的选法组成的集合,因为这i - 1个物品可以自由选择,即f(i - 1, j - vi)。所以,右边是f(i - 1, j - vi) + wi
f(i, j) = max(f(i - 1, j), f(i - 1, j - vi) + wi)
注意:当j < vi时,右边集合是不存在的
#include<iostream>
#include<algorithm>
using namespace std;const int N = 1010;
int f[N][N], v[N], w[N], n, m;int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);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 = 0;j <= m;j ++){f[i][j] = f[i - 1][j];if(j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);}cout << f[n][m] << endl;return 0;
}
代码中i、j的起始和结束看放在集合中是否有意义
优化版本
DP的优化和分析通常是分开的。DP的所有优化,都是对代码做的等价变形(与问题无关,只是对代码的实现进行了变形),只需保证优化完与原先是等价的即可。
这一题我们没办法对时间进行优化,只能对空间进行优化。
我们通过观察上面代码的状态转移方程回发现,我们在计算f[i][j]时,永远只会用到二维数组的i - 1层,所以我们没必要使用一个二维数组来存储,只需使用一个一维数组即可。倘若我们将上面代码的第一维删掉,我们可以得到:
#include<iostream>
#include<algorithm>
using namespace std;const int N = 1010;
int f[N], v[N], w[N], n, m;int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);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 = 0;j <= m;j ++){f[j] = f[j]; // f[i][j] = f[i - 1][j];if(j >= v[i]) f[j] = max(f[j], f[j - v[i]] + w[i]);// f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);}cout << f[n][m] << endl;return 0;
}
我们现在需要看一下,两断代码是否与原先是等价的。
(1)f[j] = f[j]与f[i][j] = f[i - 1][j]是否等价?
是等价的,在f[j] = f[j]中,我们算f[j]时,右边的f[j]是没有更新过的,也就是左边是第i层,右边是第i - 1层的,所以两者是等价的。并且因为f[j] = f[j]是恒成立的,所以这一步可以直接不要。
(2)下面两者是否等价?
对于max中的第一个参数并不需要管,因为只是与第二个参数作比较,看第二个参数即可。若j是从0到m递增遍历的,而j - v[i]一定小于j,此时的f[j - v[i]]是第i层的,与原先的代码不符合,为了让两者等价,需要让j从m到0递减遍历。这样才能保证f[j]是第i层时,f[j - v[i]]是i - 1层的。
#include<iostream>
#include<algorithm>
using namespace std;const int N = 1010;
int f[N], v[N], w[N], n, m;int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);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 = m;j >= 0;j --)if(j >= v[i]) f[j] = max(f[j], f[j - v[i]] + w[i]);cout << f[m] << endl;return 0;
}
此时可将判断条件放到for中
#include<iostream>
#include<algorithm>
using namespace std;const int N = 1010;
int f[N], v[N], w[N], n, m;int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);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 = m;j >= v[i];j --)f[j] = max(f[j], f[j - v[i]] + w[i]);cout << f[m] << endl;return 0;
}
还可以将v和w这两个数组优化掉,因为每次只会用到v[i]和w[i]
#include<iostream>
#include<algorithm>
using namespace std;const int N = 1010;
int f[N], v, w, n, m;int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> m;for(int i = 1;i <= n;i ++){cin >> v >> w;for(int j = m;j >= v;j --)f[j] = max(f[j], f[j - v] + w);}cout << f[m] << endl;return 0;
}
注意:只有优化时才需要考虑j从前往后遍历还是从后往前遍历,二维数组时是不需要考虑这个的
2.2 完全背包问题
3. 完全背包问题 - AcWing题库
朴素版本
完全背包问题与01背包问题是类似的,只是01背包问题对于每一个物品只能选0次或1次,而完全背包问题,每一件物品都可以选无限次。
这里的状态表示与01背包问题是完全一样的,就不过多赘述了。不同点在于状态计算。在完全背包问题中,因为每个物品是可以选无限次的,所以不能以第i件物品选或不选来对集合进行划分,而是应该按第i件物品选几次来对区间进行划分。
(1)当第i件物品不选时,此时就是在i - 1件物品中选,并让体积<=j,f(i, j) = f(i - 1, j)
(2)当第i件物品选时,此时会分成第i个物品选几次,1,2,...,k,...,n
假设第i件最多选n次,为了不失一般性,我们看第i件物品选k次的情况,假设第i件物品的体积是v,价值是w。此时可以将选k次这个集合划分成两部分,前半部分是在前i - 1物品中选,并让体积
<=j- k*v,后半部分是k个i。所以f(i,j) = f(i - 1, j - k*v) + k*w
这里的k是从0到n的,所以
f(i,j) = max( f(i - 1, j), f(i - 1, j - v) + w, f(i - 1, j - 2*v) + 2*w),...,f(i - 1, j - k*v) + k*w),...
f(i - 1, j - n*v) + n*w) )
#include<iostream>
using namespace std;
const int N = 1010;
int f[N][N];
int v[N],w[N];
int main()
{int n,m;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 = 0 ; j<=m ;j++)for(int k = 0 ; k*v[i]<=j ; k++)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 - v)等于什么
会发现圈出来的部分上面的 = 下面的 + w,下面会比上面多出来一项,但是这一项是没用的,因为背包的容量有限,第i件物品最多选n次,而多出来的一项f(i - 1, j - (n+1)*v) + w是第i件物品选n次的情况,所以是可以直接忽略的,所以:
f(i, j) = max( f(i - 1, j), f(i, j - v) + w )
#include<iostream>
#include<algorithm>
using namespace std;const int N = 1010;int f[N][N], v[N], w[N], n, m;int main()
{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 = 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]);}cout << f[n][m] << endl;return 0;
}
优化版本
对比01背包和完全背包的代码,我们会发现非常相似
f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
只有一个i - 1和i的区别。正是因为这个区别,在优化时,01背包问题的j是从大到小遍历,而完全背包问题是从小到大遍历。
#include<iostream>
#include<algorithm>
using namespace std;const int N = 1010;int f[N], v[N], w[N], n, m;int main()
{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 = 0;j <= m;j ++)if(j >= v[i]) f[j] = max(f[j], f[j - v[i]] + w[i]);cout << f[m] << endl;return 0;
}
可以将判断条件移到for循环中
#include<iostream>
#include<algorithm>
using namespace std;const int N = 1010;int f[N], v[N], w[N], n, m;int main()
{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 = v[i];j <= m;j ++)f[j] = max(f[j], f[j - v[i]] + w[i]);cout << f[m] << endl;return 0;
}
还可以将v和w这两个数组优化掉,因为每次只会用到v[i]和w[i]
#include<iostream>
#include<algorithm>
using namespace std;const int N = 1010;int f[N], v, w, n, m;int main()
{cin >> n >> m;for(int i = 1;i <= n;i ++){cin >> v >> w;for(int j = v;j <= m;j ++)f[j] = max(f[j], f[j - v]+ w);}cout << f[m] << endl;return 0;
}
2.3 多重背包问题
4. 多重背包问题 I - AcWing题库
5. 多重背包问题 II - AcWing题库
多重背包问题就是每件物品回有对应的件数
朴素版本
在所有背包问题中,状态表示都是一样的,这里就不过多赘述了。在状态计算中,也可以与前面类似,假设第i件物品的体积是v,价值是w,件数是s,根据第i件物品选几次,将集合划分成s个子集,当然不一定能够真正的划分成s个,因为背包体积是有限制的。就可以得到:
#include<iostream>
#include<algorithm>
using namespace std;const int N = 110;int f[N][N], v[N], w[N], s[N], n, m;int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);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 = 0;j <= m;j ++)for(int k = 0;k * v[i] <= j && k <= s[i];k ++)f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);cout << f[n][m] << endl;return 0;
}
时间复杂度是O(N * V * S)。在多重背包问题1中是可以的,但是在多重背包问题2中是回超时的,所以,我们要对其进行优化
二进制优化
此时和上面的完全背包问题的朴素版本一样,所以我们可能会想一样的优化方法。我们看看此时
f[i, j]与f[i, j - v]的区别
在完全背包问题中,红圈圈出来的部分中下面的式子+w就是与上面相等的,但下面的式子是比上面的式子多一项的,之所以能够相等,就是因为多出来的最后一项是没有意义的,因为以当前j的容量,最多能装n件i物品,而多出来的哪一项装了n+1件i物品,这一项的值一定0,对于取max是完全没有影响的,所以上下只相差一个w。而在多重背包问题中,多出来的这一项是有意义的,因为第i件物品的数量是有限制的,只有s件,但不代表装了s件后,不能再装,这一项代表在前i - 1件物品中选体积不超过j-(s+1)v的物品,值并不一定是0,所以会对max的取值产生影响。所以,现在是下面的除了最后一项+w就等于上面除了第1项,但f[i, j - v]是整体取max的结果,我们无法在去掉最后一项的前提下获取其他项的max,所以,无法用完全背包问题的优化思路来进行优化。
我们此时可以使用二进制优化来对其进行优化。
假设我们现在对于某一件物品的数量s = 10,我们要枚举背包中装了这件物品件数0-10次的情况,就需要从0到10次去枚举。实际上并不需要真正的去进行0-10的枚举,我们可以将这10件物品分成几个组,像这道题,我们可以分成1,2,4,3组,这样通过这些组的组合,我们也可以枚举0-10次。0=那一组都不选,1=选第1组,2=选第2组,3=第1组+第2组或直接第4组,4=选第4组,5=选第1组+第3组,6=选第2组+第3组,7=选第1组+第2组+第3组,8=选第1组+第3组+第4组,9=选第2组+第3组+第4组,10=全选。这样,我们就用4组,表示出了0-10。会发现,每一次选择,对于每一组,只有选和不选两种,这样就是一个01背包问题,并且组数是远小于s的,如s=1023,可分为1,2,4,8,...,512,此时一共就10组。
如何进行分组?
对于一个s,我们一般会分为1,2,4,...,2^k,c,满足1+2+4+...+2^k <= s,而1+2+4+...+2^k +2^(k+1) > s。要知道1+2+4+...+2^k = 2^(k+1)-1的。有了c之后,1+2+4+...+2^k+c = s。有了1,2,4,...,2^k,c后,就可以凑出0到s的任何数。比如s=200,我们可以将组分为1,2,4,8,16,32,64,73。当s = 2^(k+1)-1时,c=0,其余情况c均不为0。
分组后的时间复杂度
对于一个s,需要枚举0-s,分完组后,只会有logs个组,是以2为底的对数。所以,可以将时间复杂度从O(N * V * S)优化到O(N * V * logS)
#include<iostream>
#include<algorithm>
using namespace std;const int N = 11010;int f[N][N], v[N], w[N], n, m;int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> m;int cnt = 0;for(int i = 1;i <= n;i ++){int a, b, s;cin >> a >> b >> s; // 读入每一件物品的体积、价值和件数int k = 1; // k就是当前这一组中的件数while(k <= s){cnt ++;v[cnt] = a * k;w[cnt] = b * k;s -= k;k *= 2;}if(s > 0) // 有c的情况{cnt ++;v[cnt] = a * s;w[cnt] = b * s;}}n = cnt; // 此时的n变成了所有数都分好组后组数的总和// 接下来就是01背包问题// 每一种物品,从对应的组中进行01背包问题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 - 1][j - v[i]] + w[i]);}cout << f[n][m] << endl;return 0;
}
我们可以对这里面的01背包问题进行优化,优化步骤上面已经讲过了,这里就不过多赘述了
#include<iostream>
#include<algorithm>
using namespace std;const int N = 11010;int f[N], v[N], w[N], n, m;int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> m;int cnt = 0;for(int i = 1;i <= n;i ++){int a, b, s;cin >> a >> b >> s; // 读入每一件物品的体积、价值和件数int k = 1; // k就是当前这一组中的件数while(k <= s){cnt ++;v[cnt] = a * k;w[cnt] = b * k;s -= k;k *= 2;}if(s > 0) // 有c的情况{cnt ++;v[cnt] = a * s;w[cnt] = b * s;}}n = cnt; // 此时的n变成了所有数都分好组后组数的总和// 接下来就是01背包问题// 每一种物品,从对应的组中进行01背包问题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;return 0;
}
这里的N为什么要开到11010呢?因为在这道题中每一种物品数量的最大值是2000,分完组后最大值是11,而最多会有1000件物品,最多会有11000个组
2.4 分组背包问题
9. 分组背包问题 - AcWing题库
在分组背包问题中,状态表示与之前的有一些不一样
在状态计算中,我们是按选择第i组的第几个来划分集合的
#include<iostream>
#include<algorithm>
using namespace std;const int N = 110;int f[N], v[N][N], w[N][N], s[N], n, m;
// v、w存每一组、每一个的体积、价值,s存每一组物品的数量int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);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) // 只有当第i组,第k个物品的体积<=j时才有更新的必要f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);cout << f[m] << endl;return 0;
}
3、线性DP
线性DP是指状态转移方程有一个明显的线性关系,可以是一维、二维、多维。一般会有一个求的顺序,像背包问题是二维的,求的时候是一行一行求的。对于维度,维度是越小越好的,没多一维,时间复杂度就会增加
DP的时间复杂度计算就是状态数量 * 状态转移计算量
3.1 数字三角形
898. 数字三角形 - AcWing题库
这道题状态数量是n^2,状态转移计算量是1,所以时间复杂度是O(n^2)
这道题我们使用a数组来存储每个位置的值,f数组来表示状态,注意,在f数组初始化时,边界不能初始化为0,因为这道题的值中有负数,所以边界要初始化为负无穷
#include<iostream>
#include<algorithm>
using namespace std;const int N = 510, INF = 1e9;int a[N][N], f[N][N], n;int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n;for(int i = 1;i <= n;i ++)for(int j = 1;j <= i;j ++)cin >> a[i][j];for(int i = 0;i <= n;i ++)for(int j = 0;j <= i + 1;j ++)f[i][j] = -INF;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], 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;
}
也可以从下往上做,最后不需要枚举。
3.2 最长上升子序列
895. 最长上升子序列 - AcWing题库
896. 最长上升子序列 II - AcWing题库
子序列:从前往后,可以不连续
这里的状态计算是按第i-1个数是哪一个数来分类的。这里不是所有i前面的数都会去取max,只有当a[j] < a[i]才会取max。状态数量是n,状态转移计算量是n,所以时间复杂度是O(n^2)
#include <iostream>
#include <algorithm>using namespace std;const int N = 1010;int n;
int a[N], f[N];int main()
{scanf("%d", &n);for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);for (int i = 1; i <= n; i ++ ){f[i] = 1; // 只有a[i]一个数for (int j = 1; j < i; j ++ )if (a[j] < a[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);// printf("%d\n", *max_element(f + 1, f + n + 1));return 0;
}
现在的时间复杂度较高,所以,需要优化
会发现以3、1结尾的最长上升子序列的长度都是1,并且能放到3后面的也一定能放在1后面,而能放在1后面的不一定能放在3后面,所以3这个上升子序列是没必要存的。也就是说,当前遍历到i,i之前的都可以根据长度来划分,对于每一个长度,只需存一个结尾最小的即可。所以,可以使用一个数组来存i之前的每一个长度,对应的结尾的最小值。
会发现,结尾的最小值是随长度的增加而增加的,也就是说是单调递增的。我们可以使用反证法来证明:假设长度为5的最长上升子序列的结尾最小值<=长度为4的最长上升子序列的结尾最小值,而长度为5的最长上升子序列的倒数第二位一定是小于倒数第一位的,倒数第一位又小于长度为4的最长上升子序列的结尾最小值,此时就产生了矛盾。所以,结尾的最小值是随长度的增加而增加的
当我们遍历到ai,要将其插入到某一个子序列中,我们要找的就是结尾小于ai,并且长度最长的,接到其后面,因为是单调递增的,所以可以直接使用二分来找,找到结尾最小值中第一个小于ai的。将ai接入后,ai所在的子序列的长度就要加1,然后更新。
一共有n个数,对于每个数都要找到插入的位置,使用二分是logn,插入操作的时间复杂度是O(1),所以优化后的时间复杂度就是O(nlogn)
#include <iostream>
#include <algorithm>using namespace std;const int N = 100010;int n;
int a[N]; // 存储序列
int q[N]; // 存储不同长度下,结尾的最小值int main()
{scanf("%d", &n);for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);int len = 0; // len用来保存当前最长的上升子序列的长度for (int i = 0; i < n; i ++ ){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;}// 二分结束后,l==r,q[r]就是第一个比a[i]小的,r就是这个上升子序列的长度len = max(len, r + 1); // a[i]会链接到上升子序列的后面,所以要加1再取maxq[r + 1] = a[i]; // 更新结果}printf("%d\n", len);return 0;
}
3.3 最长公共子序列
897. 最长公共子序列 - AcWing题库
状态计算中,是按a[i]、b[j]是否包含在子序列中来划分集合的,此时有4种情况。此时所有的情况可以保证不重不漏地分到这4种情况。f[i][j]就是在这4种情况中取max
00:子序列中既没有a[i],也没有b[j],就是f[i - 1][j - 1]
11:子序列中既有a[i],也有b[j],此时只有当a[i]] == b[j]时才能有这种情况,f[i - 1][j - 1] + 1
01:没有a[i],但有b[j]的情况。此时容易想到使用f[i - 1][j],但是这是不对的,f[i - 1][j]是在第一个序列的前i-1个字母中出现,且在第二个序列的前j个字母中出现的子序列,并不是一定有b[j]的
虽然f[i - 1][j]不是准确的没有a[i],但有b[j]的情况,但是它包含了这种情况。前面有说过,不重是不一定要遵循的,比方说在a,b,c这三个数中取一个最大值,我们可以先用a,b比较,再用b,c比较,最后再比较一下先前比较的结果。所以,虽然f[i - 1][j]会比01的范围大一些,但是超过01的这些仍然在00、01、10、11的范围之内,所以是没有事的
10:类似于01,f[i][j - 1]
因为f[i - 1][j]和f[i][j - 1]都包含了00的情况,所以代码实现中00是不需要考虑的。并且注意01和10是一定有的,但是11是不一定有的,只有当a[i] == b[j]时才有11
#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;
}
4、区间DP
282. 石子合并 - AcWing题库
区间DP就是定义状态时是定义一个区间(状态表示是表示某个区间)
状态计算中,最后一步是将左边一堆和右边一堆合并,所以可以按左右两堆的分界线在哪里来划分集合
假设i和j中间有k个元素,则k = j - i + 1,可以将左右区间的元素个数分为1和k-1,2和k-2,...,k-1和1
我们计算计算第i堆石子到第j堆石子合并代价的最小值,就是左边的最小值+右边的最小值,再加i到j的石子的代价,即f[i,j] = min(f[i, k] + f[k + 1, j] + i到j的石子的代价)。其中 i到j的石子的代价可以使用前缀和来求。
状态数量是n^2,状态计算时,对于每一个状态,k的取值是[i, j - 1],到j - 1是为了保证右边至少有一堆,所以状态计算也是n。时间复杂度是O(n^3)。
这道题在计算f[i, j]时,要保证f[i, j]要用到的状态都已经计算好了,所以我们枚举时,是根据区间长度来进行枚举的。
#include <iostream>
#include <algorithm>using namespace std;const int N = 310;int n;
int s[N]; // 存储前缀和
int 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];// len是长度,不需要从1开始,因为长度是1的全歼中只有一个元素,无法分为两部分for (int len = 2; len <= n; len ++ ) for (int i = 1; i + len - 1 <= n; i ++ ) // i是起始位置{int l = i, r = i + len - 1; // 当前区间的左右端点f[l][r] = 1e8; // 需要先将f[l][r]置为一个较大的值,否则后面取min会出错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;
}
5、数位统计DP
338. 计数问题 - AcWing题库
这道题我们可以使用暴力解法,对于每一个数都去计算它的每一位,但这样显然是会超时的。
假设我们现在输入了a,b,现在要计算a到b之间的数中1的个数,我们可以先计算出1到b之间1的个数,再计算出1到a-1之间1的个数,再使用前者去减后者,即可得到a到b之间的数中1的个数,这里面有一些前缀和的思想。所以,重点就是要实现出一个能够计算1到n中每一个数出现次数的函数,所以我们实现一个函数count(n, x),计算出1到n之间所有的数中x出现的次数。假设我们现在的n=abcdefg,是一个7位数,现在要计算1到n之间的数中,1出现的次数。我们需要分别枚举1在第1位,第2位,...,第7位中的个数,再相加,就是1到n之间的所有数中,1出现的次数了。注意,我们这里是将1到n之间所有的数都当成一个7位数来算,10会变成0000010。我们现在以计算1在第4位上出现的次数为例。
对于每一次枚举,我们需要计算第一种情况和第二种情况中的一种即可,计算情况二的哪一种取决于我们计算的这一位与x的大小关系,就像上面例子中d与1的关系。注意:此时会有几种边界情况
(1)若我们计算的是0在每个数中出现的次数时,在情况一中xxx是不能从000开始的,需要从001开始,因为0000123是不合法的,此处的第4位的0并不是一个合法的位数,这个数就是123,并没有0,需要从0010123开始,此数的0就是合法的,这个数是10123。注意:我们是将1到n所有的数都认为是与n相同位数的数,像上面的例子,将1到n所有的数都认为是7位数,所以0010123的第4位确实是0。
(2)当我们计算的是0在每个数中出现的次数时,0在首位的情况是不需要计算的,即0yyyyyy是没有意义的,这里的0并不是一个合法的位置
(3)当我们在计算首位时,第一种情况是不需要考虑的,因为前方已经没有数了
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;int power10(int x) // 计算i之后的数有多少
{int res = 1;while(x --)res *= 10;return res;
}int get(vector<int>& nums, int l, int r) // 计算i之前的数是多少
{int res = 0;for (int i = l; i <= r; i++)res = res * 10 + nums[i];return res;
}int count(int n, int x) // 获取1到n中x出现的次数
{if(!n) return 0; // 如果n = 0,直接返回0,因为数据范围中最小值是1vector<int> nums; // 使用nums来保存n的每一位数,这样在后面比较n的每一位数与x的关系时更方便while(n){nums.push_back(n % 10);n /= 10;}reverse(nums.begin(), nums.end());n = nums.size();int res = 0;for(int i = 0 + !x;i < n;i ++){// 当i = 0时,是没有第一种情况的if(i > 0) // 计算第一种情况{res += get(nums, 0, i - 1) * power10(n - i - 1);if(!x) res -= power10(n - i - 1); // x=0时是从001开始的,所以要减去一个power10(n - i - 1)}// 接下来算第二种情况,d < 0时不用管,因为情况数是0if(nums[i] == x) res += get(nums, i + 1, n - 1) + 1;else if(nums[i] > x) res += power10(n - i - 1);}return res;
}int main()
{ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int a, b;while(cin >> a >> b, a || b){if(a > b) swap(a, b);for(int i = 0;i < 10;i ++)cout << count(b, i) - count(a - 1, i) << " ";cout << endl;}return 0;
}
// nums = 1 2 3 4 5 6 7
// i
6、状态压缩DP
6.1 蒙德里安的梦想
291. 蒙德里安的梦想 - AcWing题库
我们会发现,当横向的小方块放完后,纵向小方块一定只有1种情况,所以总的方案数就等于横向小方块摆法的方案数。问题就变成了只放横着的小方块,合法的方案有几种。如何判断当前方案是否合法,就是看当前方案能否用竖着的小方块填满。可以按列来看,每一列内部所有连续的空着的小方块,需要是偶数个。
状态表示中j是一个二进制数,第i-1列有伸到第i列的位用1表示,没有用0表示,存的时候是存十进制,下面的第i列的状态表示就是j就是1100
然后看状态计算,对于一个f[i, j],第i-1列伸到第i列的状态是固定的,是j,但是第i-2列伸到第i-1列的状态是不固定的,通常我们找到是最后一步不同点,所以我们可以以此来建立状态转移方程。划分集合的依据就是第i-2列伸到第i-1列的不同状态来划分的。
我们来看看第i-2列伸到第i-1列的状态可能有几种,假设有n行,也就是有n个比特位,很明显状态有2^n种。例如上面的图有四行,有四个比特位_ _ _ _,每一个都能取1或0,所以一共有16种。但注意,因为第i-1列伸到第i列的情况是固定的,所以2^n种情况并不是每一种都是合法的,我们还需要对其就行判断。
假设第i-2行伸到第i-1行的一种情况是k,f[i, j]等于所有合法的k的f[i - 1, k]的和
如何判断k和j是否合法呢?
(1)第i-2列伸到第i-1列的小方格不能和第i-1列伸到第i列的小方格位于同一行,当(j & k) == 0时满足
(2)确定了k后,则i-1列空着的位置已经确定了,看起能否用竖着的小方块填满
初始化时需要将f[0, 0]初始化为1,因为第0列不放矩形也是一种合法的状态。最终结果是f[m,0]
朴素写法
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 12, M = 1 << N;int n, m;
long long 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;st[i] = true;for (int j = 0; j < n; j ++ )if (i >> j & 1){if (cnt & 1) st[i] = false;cnt = 0;}else cnt ++ ;if (cnt & 1) st[i] = false;}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 (int k = 0; k < 1 << n; k ++ )if ((j & k) == 0 && st[j | k])f[i][j] += f[i - 1][k];cout << f[m][0] << endl;}return 0;
}
去除无效状态的优化写法
#include <cstring>
#include <iostream>
#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];
vector<int> state[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){if (cnt & 1){is_valid = false;break;}cnt = 0;}else cnt ++ ;if (cnt & 1) is_valid = false;st[i] = is_valid;}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;
}