本文篇幅有点长了...由于这两道题目有点难，想要说清楚确实需要很大量的文字逻辑推理，因为这两题我个人觉得比较相近所以放到一起了，大家可以根据目录自行选择想看的部分看。
在常规的动态规划 DP 题目中，比如背包 DP ，我们通常都是习惯于以 dp[i][j] 两个维度表示当前的“位置”和“代价”。但如果题目有其他的限制，比如在大区间内选择出最优的k 个小区间等等，这时我们就不得不在 dp 数组多开几个维度，而且还要将各种状态塞入 dp 数组维度里来保证我们计算的逻辑严密性。
这两道题目都是涉及 K 个区域的划分还有需要我们对于 dp 的状态理解更深入的题目，两题各有相似之处，看完也能更好提升做 DP 题目的思路。
洛谷P2679
题目链接：P2679 [NOIP 2015 提高组] 子串 - 洛谷
洛谷的 P2679 就是一道比较典型的题目。说实话，第一次碰到这种题，我就算能看出这用的是动态规划 DP ，也很难一下想到要怎么个思路去表示这个 dp 数组。但我们只要冷静仔细分析，就能很好看出它的做法了。
首先暴力肯定走不通的，所以我们首选当然是 DP 。那我们既然要在字符串 A 里选出一些子串组合与字符串 B 相等。所以很显然，我们的 dp 数组必然有 dp[i][j] 两个状态了。表示在字符串 A 的前 i 个字符里选出几个子串，组合起来与字符串 B 里前 j 个字符相等的方案数。
但这当然远远不够，我们做动态规划 DP 题目必须要敢于开多维的数组。不能说一直想着开三维四维的数组会不会出问题，会不会 MLE 什么的。数组大了我们后续可以优化，但我们想要做出题目， dp 数组里每一维都代表一种状态，丢失一种状态我们的状态转移就不够严密，那就推导不出结果了。
所以也很显然，我们还需要记录下我们当前已经划分出来几个子串了。所以我们的dp[i][j][k] 应该表示，在字符串 A 的前 i 个字符里选出 k 个子串，组合起来与字符串 B 里前 j 个字符相等的方案数。
到这里似乎就状态选得差不多了。但是还是不够，我们推导到了字符串 A 的第 i 个字符的时候，我们会有个疑问：这个第 i 个字符我们到底选没选？而且，可以发现当前这个字符选不选和上一个字符选没选也同样有很强烈的关系：如果这个字符我选了，上一个字符没选，那就是说明当前这个字符属于的是一个全新的子串；如果这个字符我选了，上一个字符也选了，那不就说明了这两个字符同属于一个子串里吗......
所以最后经过我们的分析，当前这个字符 i 选没选同样很重要！既然我们的推导离不开这个字符 i 选不选的状态，我们就还要新开一个状态来记录当前字符 i 我们到底选没选。所以最终的 dp 数组状态定义就如下：
1. dp[i][j][k][0] ：在字符串 A 的前 i 个字符里选出 k 个子串，且当前字符 i 没有被选择入子串（表现为0），组合起来与字符串 B 里前 j 个字符相等的方案数。
2. dp[i][j][k][1] ：在字符串 A 的前 i 个字符里选出 k 个子串，且当前字符 i 被选择入子串（表现为1），组合起来与字符串 B 里前 j 个字符相等的方案数。
虽然状态看起来很复杂，但是我们刚刚经过分析，实际上每一个状态都是不可或缺的。
现在状态充足了，我们就可以推导一下状态转移方程了。
此时其实还有一件很重要的事情，字符串 A 和字符串 B在处理到各自的 i 和 j 个字符的时候，i 字符和 j 字符是否相同呢？这个同样重要，我们需要严密的分类讨论一下。
情况一：A[i] != B[j]
先来讨论一下 i 字符和 j 字符不同的情况。
首先是 dp[i][j][k][0] ，根据我们的定义，既然当前这个字符 i 我们都没选了，那上一个字符其实选和不选都可以了，而且所有选择的子串都在前面。而且既然我们都不选第 i 个字符了，所以也不用管第 i 个字符和第 j 个字符什么关系了。所以在字符串 A 前面 i-1 个字符里，我们选出了 k 个子串组合和字符串 B 前 j 个字符串相同。所以很好推出
dp[i][j][k][0]=dp[i-1][j][k][0]+dp[i-1][j][k][1]
而 dp[i][j][k][1] ，根据定义我们选择了第 i 个字符作为子串部分，可是第 i 个字符甚至都不和字符串 B 的第 j 个字符相等？！所以答案很明显，这个状态是不合理的，选择了第 i 个字符这个字符串 A 的结尾部分作为子串部分了，而它不和字符串 B 的结尾部分第 j 个字符相等这是不合理的。所以直接得出
dp[i][j][k][1]=0
情况二：A[i] == B[j]
此时 i 字符和 j 字符相等了，可以发现，如果我们不选第 i 个字符，实际上和刚刚的推理没什么区别，直接可以得出同样的
dp[i][j][k][0]=dp[i-1][j][k][0]+dp[i-1][j][k][1]
这个 dp[i][j][k][0] 的推导比较简单，而这个 dp[i][j][k][1] 的推导就稍微有点复杂了。
正如我们刚刚所说，这个第 i 个字符选没选和上一个字符选没选很重要，决定着我们从哪里开始结束或者新开一个子串。我们想一想：既然现在我们已经选了第 i 个字符了，如果说第 i 个字符和上一个字符无关，换句话说，这第 i 个字符自己是一个新子串的开头了，那这样一来上一个字符选没选同样没关系了，上一个字符就可选可不选。上一个字符既可以不被选入子串，也可以作为上一个子串的结尾。但这次不一样了，因为这个字符 i 代表这一个新子串，所以说它占掉一个子串选择名额，留给前面 i-1 个字符的就只有 k-1 个选择了。而且由于 A[i]==B[j] ，它们目前是匹配在一个子串里的，按我们的逻辑应该是前面 i-1 个和 j-1 个进行子串选择组合匹配了，因为结尾的就是同一个新子串里的，所以上一个状态应该是dp[i-1][j-1][k-1][0] 和 dp[i-1][j-1][k-1][1] 。所以目前，我们得到一个式子：
dp[i][j][k][1]=dp[i-1][j-1][k-1][0]+dp[i-1][j-1][k-1][1]
但不能忘了我们还有一种情况。如果这个字符 i 不是一个新子串开头，而是紧接着上一个子串的末尾呢？这个时候，上一个字符也是必然属于一个子串里的，是必被选的。而且这样的话，这个字符 i 就没有占掉了我们要求的 k 个子串名额了。所以 k 个子串选择要留给了前 i-1 个字符。所以应该由状态dp[i-1][j-1][k][1]推导而来。所以最终我们可以得到
dp[i][j][k][1]=dp[i-1][j-1][k-1][0]+dp[i-1][j-1][k-1][1]+dp[i-1][j-1][k][1]
细节问题
状态转移方程推导完成后，其实这道题就没什么难度了。但是我们还需要注意几个问题。
首先就是这题的dp 数组初始化问题了，由于这题的状态定义非常复杂，所以初始化的时候我们也会有点头晕了，我们必须好好去分析。毫无疑问，dp[0][0][0][0] 肯定是要初始化为 1 的。dp[0][0][0][1]呢？其实在前两维为 0 的情况下，这个点根本就没存在意义，不用管了。我们再回忆一下我们的 dp 状态定义，如果表示字符串 B 的那一维为 0 ，也就是所有 dp[i][0][0][0] ，也要全部初始化为 1 。因为在状态的定义上，在字符串 A 的前 i 个字符选出 0 个子串而且不选第 i 个组合起来等于字符串 B 是成立的；而在逻辑上，初始化 dp[i][0][0][0] 为 0 也代表着我们其实前 i 个字符都不选为子串，也是符合逻辑的可以做到的。初始化的问题必须理清楚了，一旦漏了初始化很多地方都会出错还找不出错误的地方......
其次就是这道题想要 AC 可没这么简单。我们注意我们开的数组是四维的。一般 dp 数组来到三位四维这个位置及以上我们就几乎必须考虑进行滚动数组的优化了。我们可以发现我们的每一个关于 i 的状态都只用到了前一个 i-1 的状态推导而来，所以滚动数组是完全可行的。如果不用滚动数组，我们开的 dp 数组就是 dp[1005][205][205][2] 了。计算下来如果是 int 类型我们直接用掉了大约322 MB内存了，必然 MLE 。所以滚动数组优化几乎是必须的了。如果有对滚动数组不那么精通的读者，可以去看看我之前的一个专门讲解清楚滚动数组优化的方式的博客。链接：https://blog.csdn.net/h_a_o777oah/article/details/159437257
代码及总结
由于本人较菜，所以滚动数组我写得更好理解一点的奇偶滚动数组，感觉类似 01 背包的滚动数组写法还是有点难理解。以下是本人的代码。
#include <bits/stdc++.h> #define int long long//我用个long long怕不知道哪里爆了虽然有取模 using namespace std; const int mod=1000000007;//记得取模 int dp[2][205][205][2];//dp数组 void solve(){ int n,m,k; cin>>n>>m>>k; string a,b; cin>>a>>b; //我对字符串a和b都做了一点下标偏移，让下标从1开始而不是0开始，更符合直觉 a=" "+a; b=" "+b; dp[0][0][0][0]=1; //遍历三层 i,j,h for(int i=1;i<a.size();++i){ int ni=i&1; int bi=(i-1)&1; dp[ni][0][0][0]=1;//滚动数组每一次都得记得初始化 for(int j=1;j<b.size();++j){ for(int h=1;h<=k;++h){ //写下刚刚推导得出的状态转移方程 if(a[i]!=b[j]){ dp[ni][j][h][0]=(dp[bi][j][h][1]+dp[bi][j][h][0])%mod; dp[ni][j][h][1]=0; }else{ dp[ni][j][h][0]=(dp[bi][j][h][1]+dp[bi][j][h][0])%mod; dp[ni][j][h][1]=(dp[bi][j-1][h-1][0]+dp[bi][j-1][h-1][1]+dp[bi][j-1][h][1])%mod; } } } } cout<<(dp[n&1][m][k][1]+dp[n&1][m][k][0])%mod<<'\n';//最终答案选和不选最后一个字符都要算上 } signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int T=1; while(T--){ solve(); } }全部看下来，这道题主要的价值就是我们能否想到将当前这个字符 i 选不选这个状态变成 0 和 1 放入 dp 数组里。理解了这个，对我们后续做题会更有好处。还有就是在高度复杂的 dp 状态里处理初始化问题，这个不静下心想想真的很容易漏掉。我一开始就只想到了 dp[0][0][0][0]=1，没想到全部 dp[i][0][0][0] 都应该等于 1 。推导状态转移相比起来就容易很多了，但还是需要认真思考，第一次做不出来很正常，以后第二次碰到类似的，想必能马上推导出来的。
洛谷P2331
题目链接：P2331 [SCOI2005] 最大子矩阵 - 洛谷
经过刚刚那道题，我们看到这个题目就可能有点似曾相识的感觉了。一样都是选择 k 个，只不过一个是矩阵一个是子串。但很明显这题的相比于刚刚的就更加复杂了。矩阵和子串完全不是一个难度的东西，子串我从头扫到尾就行了，可是矩阵呢？我要多大的长宽？而且随便想想都能发现这一推导下来好像完全没有什么办法进行任意矩阵的状态转移。
但是这也不是完全没有任何办法去做。相信仔细观察都能发现，这题的m 限制要么是 1 ，要么是 2。这就给了我们一点希望了。如果 m 等于 1 ，那这题和刚刚的选择子串不是几乎一模一样的吗？唯一需要处理的，就是 m 等于 2 的情况了。
我一开始确实发现了 m 的限制特殊，可我一下也没反应过来应该分开两种情况来写，下意识以为要写一个同时适用于 m 两种情况的写法。但是其实面对这种情况限制较少的，完全可以考虑分开两种情况 m==1 和 m==2 来分别设计适合的方法。
情况一： m == 1
如果 m 等于 1 ，实际上就是和刚刚的子串选择无异了。相对来说，甚至更加简单。因为本质上，选择子串和选择子矩阵都是连续区间的嘛，所以方法也是共通的。我们只需要如下 dp 数组定义就能很快做出来了。
1. dp[i][j][0] ：在前 i 个数字里，选择 j 个子矩阵，且不选择第 i 个数字。
2. dp[i][j][1] ：在前 i 个数字里，选择 j 个子矩阵，且选择第 i 个数字。
比刚刚更加简单了，这里只有三个维度数组，只要按照刚刚子串的思路去推导状态转移方程即可。由于相对比较简单不再赘述，我们重点看 m==2 的情况。
情况二： m == 2
如果 m 等于 2 ，情况就似乎很复杂了。如果沿用刚刚 dp[i][j] 代表前 i 个数字选择 j 个子矩阵，显然状态还不够，我们需要得知最后的那个位置 i 我们是一个怎么个选择的情况。
现在 m==2 了，我们的最后位置 i 就有了两个数字，而他们分别可能处于什么状态呢？看起来很复杂，其实我们梳理清楚，会发现实际上它们只可能有五种状态关系。为了描述得更直观，在最后位置 i 的其中一个数字叫数字 a ，另一个数字叫数字 b。大家看的时候建议还是拿笔出来画一下否则纯看可能有点难理解。以下是五种状态的罗列。
为了符合数组下标，我会从下标 0 开始。
状态 0 ：a 和 b 都不被选入子矩阵中。
状态 1 ；a 被选入了子矩阵中，但 b 没有被选入。
状态 2 ；a 没有被选入子矩阵，但是 b 被选入了。
状态 3 ：a 和 b 都被选入了子矩阵中，但是它们不属于同一个子矩阵。
状态 4 ：a 和 b 同时被选入了同一个子矩阵中。
事实上，我们的选择情况就只有这五种状态而已，不会再有其他状态了。
所以，我们既然发现了状态其实就这几个，我们完全可以直接在 dp 数组新开一维表示状态 0-4。最终，我们的 dp 数组定义就可以直接确定了。
dp[i][j][k] ：在前 i 个数字里，选择出 j 个子矩阵，且目前最后位置 i 的两个数字处于状态 k 。
这些状态实在非常复杂，我们需要一个个去推导才行。所以做题还是推荐把状态 0-4 分别代表什么写在纸上，这样就不会绕晕了。
状态 0
回忆一下，状态 0 代表的是 a 和 b 都不被选入子矩阵中。那既然 a 和 b 都和我们的子矩阵无关了，那它上一个状态 i-1 就可以是 0-4 的任意一个状态了。而且 a 和 b 没有占任何子矩阵的名额。所以答案很简单。
dp[i][j][0]=max( dp[i-1][j][0] , dp[i-1][j][1] , dp[i-1][j][2] , dp[i-1][j][3] , dp[i-1][j][4] )
状态 1
状态 1 我们选择了数字 a ，所以我们就要记得把这个对应的数字加入 dp 值里了。但是我们还需要注意一个问题：选择的数字 a 到底是承接上一个子矩阵，还是它自己单独成为一个子矩阵的开头？
如果它要单独做一个子矩阵的开头，那么其实上一个状态 i-1 选择什么同样和它无关了，可以是状态 0-4 任意一个。唯一不同的是它占掉了一个子矩阵的选择名额，所以上一个状态应该变成 j-1 了。
dp[i][j][1]=max( dp[i-1][j-1][0] , dp[i-1][j-1][1] , dp[i-1][j-1][2] , dp[i-1][j-1][3] , dp[i-1][j-1][4] ) + a
如果说它要承接上一个子矩阵，那我们就能知道，那上一个状态中就必须要选择数字 a 了，而数字 b 就是可选可不选。根据定义，符合情况的只有 1 和 3 。十分要注意的是 4 绝对不行！因为状态 4 中 a 和 b 是属于同一个矩阵的。如果由状态 4 推导而来，那我们的矩阵就会变成如下图。
这样绝对不符合矩阵的定义，不合法。
所以我们还有两个状态不能遗漏了。
dp[i][j][1]=max( dp[i-1][j][1] , dp[i-1][j][3] ) + a
综合起来即可。
状态 2
状态 2 是只选 b 不选 a ，实际上和状态 1 没什么区别。首先是如果是新开子矩阵与之前状态无关，和状态 1 的推导是一样的。
dp[i][j][2]=max( dp[i-1][j-1][0] , dp[i-1][j-1][1] , dp[i-1][j-1][2] , dp[i-1][j-1][3] , dp[i-1][j-1][4] ) + b
如果与之前状态有关，是承接上一个子矩阵，那也是只有 2 和 3 状态是符合的，切记状态 4 不会符合，和状态 1 的时候原理一样。
dp[i][j][2]=max( dp[i-1][j][2] , dp[i-1][j][3] ) + b
状态 3（重要易错）
状态 3 就稍微复杂了。主要是 a 和 b 是各自为政的，我们很容易会漏掉一些情况！
首先就是a 和 b 都与前面的无关，都是新开矩阵，那么上一个的状态和刚刚完全一样，就和它毫无关系了。但是要注意的是这样一来我们 a 和 b 都会各自占据一个子矩阵名额，那就是留给前面的 i-1 就只有 j-2 个了。写代码的时候我们也要记得加上判断 j>=2 ，否则就越界访问数组了。
dp[i][j][3]=max( dp[i-1][j-2][0] , dp[i-1][j-2][1] , dp[i-1][j-2][2] , dp[i-1][j-2][3] , dp[i-1][j-2][4] ) + a + b
如果a 和 b 都是与前面有关的，承接之前的子矩阵，那也就是说，前面的 i-1 状态的 a 和 b 也要被选择，而这种情况下只有状态 3 和 4 。而很明显，状态 4 是不符合逻辑的。所以这种情况只能由上一次的状态 3 转移而来。而且我们是没有消耗子矩阵划分名额，所以 j 不用变。但是由于这种情况下，按照逻辑 j 起码也要大于 2 了，所以我们最好还是写入判断 j>=2 的 if 判断里。
dp[i][j][3]=max( dp[i-1][j][3] ) + a + b
而还有一种情况就是a 和 b 之中有一个和之前的有关，承接之前的子矩阵，而另一个是自己新开一个矩阵。这样就有点复杂了。首先我们确定，我们这种情况会有一个新开矩阵，那么留给之前的子矩阵名额就只有 j-1了。那么很好发现，如果是 a 是新开的那个子矩阵，那么来源状态可以是dp[i-1][j-1][1] 和 dp[i-1][j-1][3]；如果 b 是新开的子矩阵，那么来源状态就是dp[i-1][j-1][2] 和 dp[i-1][j-1][3]。所以我们这个情况的状态转移方程就是
dp[i][j][3]=max( dp[i-1][j-1][1] , dp[i-1][j-1][2] , dp[i-1][j-1][3] ) + a + b
状态 3 的情况很容易遗漏，我在状态 3 这里就出错了，所以这个状态 3 的推导还是比较重要的，一定要找到所有情况。
状态 4
状态 4 就比较简单了，首先还是选择的 a 和 b 作为一整个新子矩阵，它们占掉一个子矩阵名额且与之前的无关，可以由之前的任意状态推导而来。
dp[i][j][4]=max( dp[i-1][j-1][0] , dp[i-1][j-1][1] , dp[i-1][j-1][2] , dp[i-1][j-1][3] , dp[i-1][j-1][4] ) + a + b
状态 4 里 a 和 b 是绑定一块的，所以它如果是承接于上一个状态，那么只能是同时都于上个状态有关，而且上个状态也只能是状态 4 了。如果上个状态是状态 3 显然不合理。
dp[i][j][4]=max( dp[i-1][j][4] ) + a + b
代码及总结
最终，我们的状态推导就完成了。可以看到，我们的状态推导出来还是挺多东西的，所以我做题写的时候还要写上注释不然写着写着都不知道写到哪了。而且 m==1 和 m==2 的两种情况实际上用到的数组差不多，我们可以按照 m==2 这么大的数组开出来， m==1 利用其中部分就行了。初始化也是和刚刚的字串一样，必须注意这些细节。以下是我的代码。
#include <bits/stdc++.h> using namespace std; const int maxn=2e5+5; int dp[105][15][5]; int arr[105][2];//arr[i][0]是a,arr[i][1]是b,m==1的时候只用arr[i][0] void solve(){ int n,m,k; cin>>n>>m>>k; memset(dp,0xc0,sizeof(dp));//求最大值全部初始化为0 for(int i=0;i<=n;++i) dp[i][0][0]=0;//初始化 //m==1和子串的逻辑基本一样 if(m==1){ for(int i=1;i<=n;++i){ cin>>arr[i][0]; } for(int i=1;i<=n;++i){ for(int j=1;j<=k;++j){ dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j][1]); dp[i][j][1]=max(max(dp[i-1][j-1][0],dp[i-1][j-1][1]),dp[i-1][j][1])+arr[i][0]; } } cout<<max(dp[n][k][0],dp[n][k][1])<<'\n'; }else{ //m==2的状态极多一定要分清楚 for(int i=1;i<=n;++i){ cin>>arr[i][0]>>arr[i][1]; } for(int i=1;i<=n;++i){ for(int j=1;j<=k;++j){ //状态0 for(int h=0;h<5;++h) dp[i][j][0]=max(dp[i][j][0],dp[i-1][j][h]); //状态1新开矩阵与上一个无关 for(int h=0;h<5;++h) dp[i][j][1]=max(dp[i][j][1],dp[i-1][j-1][h]+arr[i][0]); //状态1与上一个有关 dp[i][j][1]=max(dp[i][j][1],max(dp[i-1][j][1],dp[i-1][j][3])+arr[i][0]); //状态2与上一个无关 for(int h=0;h<5;++h) dp[i][j][2]=max(dp[i][j][2],dp[i-1][j-1][h]+arr[i][1]); //状态2与上一个有关 for(int h=2;h<4;++h) dp[i][j][2]=max(dp[i][j][2],dp[i-1][j][h]+arr[i][1]); //状态3 if(j>=2){ //状态3与上一个同时无关 for(int h=0;h<5;++h) dp[i][j][3]=max(dp[i][j][3],dp[i-1][j-2][h]+arr[i][1]+arr[i][0]); //状态3与上一个同时有关 dp[i][j][3]=max(dp[i][j][3],dp[i-1][j][3]+arr[i][1]+arr[i][0]); } //一个有关一个无关 dp[i][j][3]=max(dp[i][j][3],max(dp[i-1][j-1][1],max(dp[i-1][j-1][3],dp[i-1][j-1][2]))+arr[i][1]+arr[i][0]); //状态4与上一个无关 for(int h=0;h<5;++h) dp[i][j][4]=max(dp[i][j][4],dp[i-1][j-1][h]+arr[i][1]+arr[i][0]); //状态4与上一个有关 dp[i][j][4]=max(dp[i][j][4],dp[i-1][j][4]+arr[i][1]+arr[i][0]); } } int ans=-1e9; for(int i=0;i<5;++i) ans=max(ans,dp[n][k][i]);//从5种状态中得出最大值 cout<<ans<<'\n'; } } signed main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int T=1; //cin>>T; while(T--){ solve(); } }总结下来，这两道题目其实都是差不多类型的 k 个划分 DP 。而且基本都是要求我们在 DP 的时候要记录状态。比如 P2331 中就可以直接用几个数字来代表所属的状态了。特别之后看到这种类似选 k 次，且当前决策会锁定后续连通性的题目，，其底层逻辑必然坍缩为状态机映射。希望大家看完可以彻底明白这种 DP 的思维！
