以上回文串解释了回文串的构成。当回文串的长度为奇数时，长度为1肯定是回文的，长度n大于1时，中心点为 $n/2$ （向下取整，下标从0开始）左右分布对应字符串对应相等如aba；当回文串为偶数时，长度为2时，左边起点定义为l，右边起点定义为r，l+1=r，长度大于2时，左边起点定义为l，右边起点定义为r，

s[l+i]=s[r-i],\qquad 0\le i<\left\lfloor\frac{r-l+1}{2}\right\rfloor

如abba

变成回文串的最小开销#

bca ->bcacb / acbca 2
bcab -> bcacb / bacab 1

基于以上分析，发现变成回文串的诀窍在于补充对应位置上的字符，并且发现利用中心的特性可以少用一个开销（虽然说用不上）并且存在某种意义上的对称性，从最左边l最右边r开始扫描，如果对应，则l++，r—，如果不对应，有两种尝试方式：

补充左边对应位置的字符，逻辑上说就是r+1上补充l位置的字符，那么l解决了问题l++，r没有对称，不变r
同理补右边，l，r—

那么就存在了递归的可能性，可以通过记忆化搜索解决这个问题

1
int dfs(string s,int l,int r){ // 基于以上分析写的暴力
2
  if(l==r){  // a
3
    return 0;
4
  }
5
  if(l+1==r){ // aa
6
    return s[l]==s[r]?0:1;
7
  }
8
  if(s[l]==s[r]){ // 相等情况下
9
    return dfs(s,l+1,r-1);
10
  }
11
  else{  // 不相等
12
    return min(dfs(s,l,r-1),dfs(s,l+1,r))+1;
13
  }
14
}

记忆化搜索解#

1
int minInsertions(string s) {
2
  int n=s.size();
3
  vector<vector<int>> dp(n,vector<int>(n,-1));
4
  auto mems = [&](auto&& self,int l,int r)->int{
5
    if(dp[l][r]!=-1) return dp[l][r];
6
    int ans;
7
    if(l==r){
8
      ans=0;
9
    }
10
    else if(l+1==r){
11
      ans=(s[l]==s[r]?0:1);
12
    }
13
    else{
14
      if(s[l]==s[r]){
15
        ans=self(self,l+1,r-1);
16
      }
17
      else{
18
        ans=min(self(self,l+1,r),self(self,l,r-1))+1;
19
      }
20
    }
21
    dp[l][r]=ans;
22
    return ans;
23
  };
24

25
  return mems(mems,0,n-1);
26
}

递推解#

根据刚刚的分析，我们会先聚焦到某一个单独的字符或者两个字符。边界值就是单个字符和两个字符的情况，单个字符的代价一定为0，两个字符相等为0，不相等为1，然后其他情况开始判断是否 $s[l]==s[r]$ 是的话，说明对应位置是相等的，代价为0，那么这个位置的答案就等于他的里面字串的情况就是 $dp[l+1][r-1]$ ；不是的话，那么他需要选择上述两种尝试方式的代价其中一个，代价都是1，选择第一个方式，那么就是选择 $dp[l+1][r]$ ，如果选择第二种方式，那么就是选择 $dp[l][r-1]$ 。（解释见补充）为了使答案最小，那么选择的是两种方式中小的那个情况，整理一下就是 $min(dp[l+1][r],dp[l][r-1])+1$ 。那么整个dp表纵坐标可以表示l，横坐标可以表示r，那么遍历顺序就是r从0到n-1,l从r到0的双层循环因此dp状态 $dp[l][r]=\text{将子串 }s[l..r]\text{ 变成回文串所需的最少插入次数}$ 结果从l到r，也就是从0到n-1就是 $dp[0][n-1]$ 状态转移方程如下：

$dp[l][r]= \begin{cases} 0,&l=r\\ 0,&r=l+1\text{ 且 }s[l]=s[r]\\ 1,&r=l+1\text{ 且 }s[l]\ne s[r]\\ dp[l+1][r-1],&s[l]=s[r]\\ \min(dp[l+1][r],dp[l][r-1])+1,&s[l]\ne s[r] \end{cases}$

1
int minInsertions(string s) {
2
  int n=s.size();
3
  vector<vector<int>> dp(n,vector<int>(n,-1));
4
  for(int r=0;r<n;r++){
5
    for(int l=r;l>=0;l--){
6
      if(l==r) dp[l][r]=0;
7
      else if(r-l==1){
8
        dp[l][r]=s[l]==s[r]?0:1;
9
      }
10
      else{
11
        if(s[l]==s[r]) dp[l][r]=dp[l+1][r-1];
12
        else dp[l][r]=min(dp[l+1][r],dp[l][r-1])+1;
13
      }
14
    }
15
  }
16
  return dp[0][n-1];
17
}

补充#

虽然不理解不影响过题，但是还是补充一下为什么：

这里的 $dp[l][r]$ 表示将原字符串的子串 $s[l\dots r]$ 变成回文串所需的最少插入次数。DP 下标只记录原字符串的区间，后来插入的字符只会产生 $1$ 的代价，不会进入新的 DP 状态。

当 $s[l]\ne s[r]$ 时，两个原端点无法直接配对，因此有两种选择：

在右侧插入 $s[l]$

结构变为：
$\underbrace{s[l]}_{\text{原左端}}\quad \underbrace{s[l+1]\dots s[r]}_{\text{剩余的原子串}}\quad \underbrace{s[l]}_{\text{新插入}}$
原来的左端点 $s[l]$ 和新插入的 $s[l]$ 已经形成一对回文字符。去掉这对已经解决的字符后，剩下的原字符串区间是 $[l+1,r]$ ，所以这种选择的代价为：
$dp[l+1][r]+1$
在左侧插入 $s[r]$

结构变为：
$\underbrace{s[r]}_{\text{新插入}}\quad \underbrace{s[l]\dots s[r-1]}_{\text{剩余的原子串}}\quad \underbrace{s[r]}_{\text{原右端}}$
新插入的 $s[r]$ 和原来的右端点 $s[r]$ 已经形成一对回文字符。去掉这对已经解决的字符后，剩下的原字符串区间是 $[l,r-1]$ ，所以这种选择的代价为：
$dp[l][r-1]+1$

为了使插入次数最少，在两种选择中取最小值：

dp[l][r]=\min(dp[l+1][r],dp[l][r-1])+1

可以记成：在右边插入左端字符，就解决原左端点；在左边插入右端字符，就解决原右端点。

486. 预测赢家 #

区间dp+博弈dp。因为每次拿取都是在端点上拿取，所以符合区间dp的特性，并且两个人不仅要让自己得到的分数最大，还要不让对方拿到更大的点数，因此不是盲目拿取最大的点数，存在博弈策略：在尽可能不让别人拿到更大的优势下选择更大的点数。暴力递归代码如下：

1
int solve(int l,int r){
2
  if(l==r){  // 只剩一个，别无选择
3
    return nums[l];
4
  }
5
  if(l+1==r){ // 只剩两个，局部贪心拿最大
6
    return max(nums[l],nums[r]);
7
  }
8
  /*
9
  博弈核心：对方选取最有利的情况 就是自己最差的情况
10
  已知当前的所有抉择中最差的情况中找相对更好的情况
11
  */
12
  return max(
13
    nums[l]+min(solve(l+2,r),solve(l+1,r-1)),
14
    nums[r]+min(solve(l+1,r-1),solve(l,r-2))
15
  );
16
}

记忆化搜索解：

1
bool predictTheWinner(vector<int>& nums) {
2
  int n=nums.size(),sum=0;
3
  for(int i=0;i<n;i++) sum+=nums[i];
4
  vector<vector<int>> dp(n,vecctor<int>(n,-1));
5
  auto mems = [&](auto&& self,int l,int r)->int{
6
    if(dp[l][r]!=-1){
7
      return dp[l][r];
8
    }
9
    if(l==r) return nums[l];
10
    if(l+1==r) return max(nums[l],nums[r]);
11
    return max(
12
      nums[l]+min(self(self,l+2,r),self(self,l+1,r-1)),
13
      nums[r]+min(self(self,l+1,r-1),self(self,l,r-2))
14
    );
15
  };
16
  int ans=mems(mems,0,n-1);
17
  return ans>=sum-ans;     // p2=sum-p1得分
18
}

递推解

1
bool predictTheWinner(vector<int>& nums) {
2
  int n=nums.size(),sum=0;
3
  for(int i=0;i<n;i++) sum+=nums[i];
4
  vector<vector<int>> dp(n,vector<int>(n,-1));
5
  // 由于要取到l+2，r-2这种数据，所以要预处理
6
  for(int l=0;l<n;l++){
7
    dp[l][l]=nums[l];
8
  }
9
  for(int r=1;r<n;r++){
10
    dp[r-1][r]=max(nums[r-1],nums[r]);
11
  }
12
  for(int r=2;r<n;r++){
13
    for(int l=r-2;l>=0;l--){
14
      dp[l][r]=max(
15
        nums[l]+min(dp[l+2][r],dp[l+1][r-1]),
16
        nums[r]+min(dp[l+1][r-1],dp[l][r-2])
17
      );
18
    }
19
  }
20
  return dp[0][n-1]>=sum-dp[0][n-1];
21
}

1039. 多边形三角剖分的最低得分 #

一个封闭多边形以任意顶点到其他任意顶点的直线（即分割线）有n-1条，其中能构成三角形的只有n-3条将图形分成n-2个三角形，并且不能相交，那么分割线就是可枚举的，每划出一条分割线将整个图形分成了两个部分，三个状态：分割线左边部分、当前l，i，r组成的三角形的值、分割线右边部分，很明显的重叠子问题，状态转移见代码

记忆化搜索解#

1
int minScoreTriangulation(vector<int>& values) {
2
    int n=values.size();
3
  vector<vector<int>> dp(n,vector<int>(n,-1));
4
  auto mems = [&](auto&& self,int l,int r)->int{
5
    if(dp[l][r]!=-1) return dp[l][r];
6
    if(l==r||l+1==r) return 0;
7
    int ans=MAXN;
8
    for(int i=l+1;i<r;i++){
9
      ans=min(
10
        ans,
11
        self(self,l,i)+self(self,i,r)+values[l]*values[i]*values[r]
12
      );
13
    }
14
    dp[l][r]=ans;
15
    return ans;
16
  };
17
  return mems(mems,0,n-1);
18
}

P1775 石子合并（弱化版） - 洛谷 #

区间dp+前缀和

1
```cpp
2
int n;
3

4
void solve(){
5
  cin>>n;
6
  vector<int> a(n+1,0);
7
  for(int i=1;i<=n;i++){
8
    cin>>a[i];
9
    a[i]+=a[i-1];
10
  }
11
  vector<vector<int>> dp(n+1,vector<int>(n+1,MAXN));
12
  for(int r=1;r<=n;r++){
13
    for(int l=r;l>=1;l--){
14
      if(l==r) dp[l][r]=0;
15
      else{
16
        for(int k=l;k<r;k++){
17
          dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]);
18
        }
19
        dp[l][r]+=a[r]-a[l-1];
20
      }
21
    }
22
  }
23
  cout<<dp[1][n];
24
}

如果这篇文章对你有帮助，欢迎分享给更多人！

动态规划-区间dp

https://blog.hydrodyio.xyz/posts/动态规划-区间dp/

作者

Hydroiody

发布于

2026-08-09

许可协议

CC BY-NC-SA 4.0

部分信息可能已经过时

数据结构-单调栈

vsc/Linux终端个性化设置

Welcome!

文章更新热度

例题#

1312. 让字符串成为回文串的最少插入次数 #

回文串分析#

变成回文串的最小开销#

记忆化搜索解#

递推解#

补充#

486. 预测赢家 #

1039. 多边形三角剖分的最低得分 #

记忆化搜索解#

P1775 石子合并（弱化版） - 洛谷 #

目录

Welcome!

例题#

1312. 让字符串成为回文串的最少插入次数#

回文串分析#

变成回文串的最小开销#

记忆化搜索解#

递推解#

补充#

486. 预测赢家#

1039. 多边形三角剖分的最低得分#

记忆化搜索解#

P1775 石子合并（弱化版） - 洛谷#

目录

1312. 让字符串成为回文串的最少插入次数 #

486. 预测赢家 #

1039. 多边形三角剖分的最低得分 #

P1775 石子合并（弱化版） - 洛谷 #