2026/4/12/周日下午笔记(划分型DP)
动态规划经典题型笔记
整理了四道动态规划经典题目，涵盖字符串拆分、回文处理、分组优化三大类，包含核心思路、代码逻辑、易错点与重点总结。
一、单词拆分（可行性判断）
题目类型
动态规划 - 字符串拆分可行性判定
核心思路
定义 dp[i] 表示字符串前 i 个字符是否能被字典中的单词拆分，通过枚举分割点 j，结合字典查询完成状态转移。
代码逻辑
#include<bits/stdc++.h>
using namespace std;
int g,n;
string a,b[1010];
int main(){
cin>>g;
while(g--){
cin>>a>>n;
a='@'+a; // 下标偏移，从1开始
map<string,int> c;
int dp[310]={1}; // dp[0]=1（空字符串可拆分）
for(int i=1;i<=n;i++){
cin>>b[i];
c[b[i]]=1; // 字典存入map
}
for(int i=1;i<a.size();i++){
for(int j=0;j<i;j++){
if(dp[j]){
string t=a.substr(j+1,i-j); // 子串a[j+1..i]
if(c[t]) dp[i]=1;
}
}
}
cout<<(dp[a.size()-1]?"true":"false")<<"\n";
}
return 0;
}
易错点
- 下标处理：通过
a='@'+a将下标从1开始，注意substr(起始位置, 长度)的参数。 - 初始化：仅
dp[0]=1，其余需初始化为0，避免未定义行为。 - 多组测试用例：每组需重新定义
map和dp数组，防止数据污染。
重点总结
- 状态定义：
dp[i]表示前i个字符的拆分可行性。 - 转移方程：
dp[i] = dp[j] && check(a[j+1..i])（check为字典查询）。 - 时间复杂度：O(L²)（L为字符串长度），配合
map/unordered_map优化查询。
二、单词拆分（最小拆分次数）
题目类型
动态规划 - 字符串拆分最优解（最小次数）
核心思路
定义 dp[i] 表示前 i 个字符的最小拆分次数（初始 dp[0]=1，最终结果需减1抵消偏移），通过枚举分割点 j 取最小值。
代码逻辑
#include<bits/stdc++.h>
using namespace std;
int n;
string a,b[1010];
int main(){
cin>>a>>n;
a='@'+a;
map<string,int> c;
int dp[310]={1}; // dp[0]=1（虚拟起始点）
for(int i=1;i<=n;i++){
cin>>b[i];
c[b[i]]=1;
}
for(int i=1;i<a.size();i++){
for(int j=0;j<i;j++){
if(dp[j]){
string t=a.substr(j+1,i-j);
if(c[t]){
if(dp[i]) dp[i]=min(dp[i],dp[j]+1);
else dp[i]=dp[j]+1;
}
}
}
}
cout<<dp[a.size()-1]-1; // 抵消初始偏移
return 0;
}
易错点
- 初始值含义：
dp[0]=1是虚拟起始点，实际拆分次数需减1。 - 状态转移：需先判断
dp[j]非0（前j个字符可达），再更新dp[i]。 - 未初始化处理：若
dp[i]为0（未可达），需直接赋值而非取min。
重点总结
- 状态定义：
dp[i]表示前i个字符的最小拆分次数（含初始偏移）。 - 转移方程：
dp[i] = min(dp[i], dp[j] + 1)（当子串a[j+1..i]合法时）。 - 结果处理：最终答案需减1，消除
dp[0]=1的初始偏移。
三、回文串最小分割次数
题目类型
动态规划 - 回文子串预处理 + 最小分割
核心思路
分两步：
- 预处理
dp1[j][i]：表示子串a[j..i]是否为回文。 - 定义
dp[i]：表示前i个字符的最小分割次数，结合回文预处理结果完成转移。
代码逻辑
#include<bits/stdc++.h>
using namespace std;
string a;
int n,dp[2010]={1},dp1[2010][2010];
int main(){
cin>>a;
n=a.size();
a='@'+a;
// 1. 预处理回文子串
for(int i=1;i<=n;i++){
dp1[i][i]=1; // 长度为1的回文
if(a[i-1]==a[i]) dp1[i-1][i]=1; // 长度为2的回文
}
for(int i=3;i<=n;i++){ // 长度≥3的回文
for(int j=1;j<=n-i+1;j++){
int k=i+j-1; // 结束位置
if(a[j]==a[k]&&dp1[j+1][k-1]) dp1[j][k]=1;
}
}
// 2. 求最小分割次数
for(int i=1;i<=n;i++){
for(int j=0;j<i;j++){
if(dp[j]&&dp1[j+1][i]){
if(dp[i]) dp[i]=min(dp[i],dp[j]+1);
else dp[i]=dp[j]+1;
}
}
}
cout<<dp[n]-2; // 抵消偏移（分割次数=段数-1）
return 0;
}
易错点
- 回文预处理下标：长度为
i，起始位置j，结束位置i+j-1，注意边界。 - 结果偏移：
dp[0]=1且分割次数 = 段数 - 1，最终需减2。 - 回文长度顺序：从短到长预处理，确保长回文依赖的短回文已计算。
重点总结
- 两步DP：先预处理回文子串，再求最小分割。
- 回文转移：
dp1[j][k] = (a[j]==a[k]) && dp1[j+1][k-1]（k为结束位置）。 - 分割转移：
dp[i] = min(dp[i], dp[j] + 1)（当a[j+1..i]是回文时）。
四、最大平均值分组
题目类型
动态规划 - 分组最优解（最大平均和）
核心思路
定义 dp[i][j] 表示前 i 个元素分成 j 组的最大平均和，通过前缀和优化区间平均值计算，枚举分组点 k 完成转移。
代码逻辑
#include<bits/stdc++.h>
using namespace std;
int n,K;
double a,s[1010],dp[1010][60];
int main(){
cin>>n>>K;
for(int i=1;i<=n;i++){
scanf("%lf",&a);
s[i]=s[i-1]+a; // 前缀和
dp[i][1]=s[i]/i; // 分成1组的平均值
}
for(int i=1;i<=n;i++){
for(int j=2;j<=K;j++){
if(j>i) break; // 分组数不能超过元素数
for(int k=j;k<=i;k++){ // 第j组的起始位置k
double avg=(s[i]-s[k-1])/(i-k+1);
dp[i][j]=max(dp[i][j],dp[k-1][j-1]+avg);
}
}
}
printf("%.6lf",dp[n][K]);
return 0;
}
易错点
- 分组数限制：
j > i时无意义，需break。 - 前缀和正确性：
s[i]需正确累加，避免下标错误。 - 初始化：仅
dp[i][1]有值，其余建议初始化为极小值（代码依赖默认值，需注意边界）。
重点总结
- 状态定义：
dp[i][j]表示前i个元素分成j组的最大平均和。 - 转移方程：
dp[i][j] = max(dp[k-1][j-1] + avg(k, i))（k为第j组起始位置）。 - 优化：前缀和快速计算区间和，降低平均值计算复杂度。
通用重点总结
- 状态定义：明确
dp[i]/dp[i][j]的含义，是“可行性”“次数”还是“最优值”。 - 下标处理：通过偏移（如
a='@'+a）简化边界判断，注意substr、前缀和的下标。 - 初始化：根据状态定义设置初始值（如
dp[0]=1表示空字符串/虚拟起点）。 - 转移顺序：确保计算当前状态时，依赖的子状态已计算完成（如回文从短到长）。
- 结果处理：注意初始偏移、定义差异（如分割次数=段数-1），需对最终
dp值做调整。