区间DP第1课：通过一个案例深入浅出研究区间DP

区间DP第1课：通过一个案例深入浅出研究区间DP

一、什么是区间DP

区间动态规划是动态规划的一种特殊形式，用于解决涉及连续区间的最优化问题。它通过将问题分解为相互重叠的连续子区间，并逐步合并这些子区间来解决整个问题。

核心特征

• 问题涉及序列或区间
• 最优解可以通过合并相邻区间得到
• 通常用二维数组dp[i][j]表示区间[i, j]的最优解

二、基本思想与模板

1. 状态定义

// dp[i][j] 表示区间 [i, j] 上的最优解intdp[n][n];

2. 通用解法框架

// 1. 初始化：长度为1的区间for(inti=0;i<n;i++){dp[i][i]=初始值;}// 2. 按区间长度从小到大递推for(intlen=2;len<=n;len++){// 区间长度for(inti=0;i+len-1<n;i++){// 区间起点intj=i+len-1;// 区间终点// 3. 初始化当前区间（根据问题决定初始值）dp[i][j]=INF 或0;// 4. 枚举分割点，将区间分成两部分for(intk=i;k<j;k++){// 状态转移dp[i][j]=min/max(dp[i][j],dp[i][k]+dp[k+1][j]+合并代价);}}}

三、常见问题类型与状态定义

本次课的研究案例

题目描述

设有N ( N ≤ 300 ) N(N \le 300)N(N≤300)堆石子排成一排，其编号为1 , 2 , 3 , ⋯ , N 1,2,3,\cdots,N1,2,3,⋯,N。每堆石子有一定的质量m i ( m i ≤ 1000 ) m_i\ (m_i \le 1000)mi​(mi​≤1000)。现在要将这N NN堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻。合并时由于选择的顺序不同，合并的总代价也不相同。试找出一种合理的方法，使总的代价最小，并输出最小代价。

输入格式

第一行，一个整数N NN。

第二行，N NN个整数m i m_imi​。

输出格式

输出文件仅一个整数，也就是最小代价。

输入输出样例 1

输入 1

4 2 5 3 1

输出 1

22

思路分析

1. 问题建模

• 目标：将N堆相邻石子合并为一堆，要求合并总代价最小
• 限制：每次只能合并相邻两堆，合并代价为两堆质量之和
• 输入：石子数量n，每堆石子质量数组a[]
• 输出：最小合并代价

2. 核心算法：区间动态规划

• 状态定义：dp[i][j]表示合并第i堆到第j堆石子的最小代价

• 边界条件：当i=j时（单堆石子），dp[i][i] = 0

• 状态转移：

  枚举区间[i,j]的分割点k:dp[i][j]=min{dp[i][k]+dp[k+1][j]}+sum(i,j)(i ≤ k<j)

  其中sum(i,j)表示区间[i,j]石子总质量，通过前缀和数组O(1)计算

3. 前缀和

• sum数组：预处理前缀和数组，sum[i] = a[1]+a[2]+...+a[i]
• 快速计算区间和：sum[j] - sum[i-1]可快速得到区间[i,j]的总质量

4. 算法流程

1. 预处理前缀和数组
2. 初始化DP边界条件
3. 枚举区间长度（从2到n）
4. 枚举区间起点
5. 枚举区间分割点
6. 根据状态转移方程更新DP表

5. 复杂度分析

• 时间复杂度：O(n³) → 三重循环（n≤300时可接受）
• 空间复杂度：O(n²) → DP表存储

AC代码

#include<bits/stdc++.h>usingnamespacestd;intn,a[310],sum[310];// a[]存储每堆石子质量，sum[]为前缀和数组intdp[310][310];// dp[i][j]表示合并区间[i,j]的最小代价intmain(){cin>>n;// 读取数据并计算前缀和for(inti=1;i<=n;i++){cin>>a[i];sum[i]=sum[i-1]+a[i];// sum[i]表示前i堆石子的总质量}// 初始化DP数组为无穷大（表示未计算状态）memset(dp,0x3f,sizeof(dp));// 单个石子堆无需合并，代价为0for(inti=1;i<=n;i++){dp[i][i]=0;}// 区间DP核心算法for(intlen=2;len<=n;len++){// 枚举区间长度for(inti=1;i<=n+1-len;i++){// 枚举区间起点intj=i+len-1;// 计算区间终点for(intk=i;k<j;k++){// 枚举分割点// 状态转移方程：合并[i,k]和[k+1,j]的代价 + 当前合并的总质量dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);}}}cout<<dp[1][n]<<endl;// 输出合并全部石子的最小代价return0;}

总结

区间DP是信奥赛中非常重要且常见的题型，掌握其核心思想"小区间合并成大区间"是关键。解题步骤通常是：

1. 识别问题是否具有区间性质
2. 定义dp[i][j]状态
3. 确定状态转移方程（如何通过分割点合并小区间）
4. 确定遍历顺序和初始化
5. 考虑优化（四边形不等式、前缀和等）

完整系列资料，请查看专栏：《csp信奥赛C++动态规划》
https://blog.csdn.net/weixin_66461496/category_13096895.html

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

• 一、CSP信奥赛C++通关学习视频课：
  • C++语法基础
  • C++语法进阶
  • C++算法
  • C++数据结构
  • CSP信奥赛数学
  • CSP信奥赛STL
• 二、CSP信奥赛C++竞赛拿奖视频课：
  • 信奥赛csp-j初赛高频考点解析
  • CSP信奥赛C++复赛集训课（12大高频考点专题集训）
• 三、考级、竞赛刷题题单及题解：
  • GESP C++考级真题题解
  • CSP信奥赛C++初赛及复赛高频考点真题解析
  • CSP信奥赛C++一等奖通关刷题题单及题解

详细内容：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

3、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

• 2025 csp-j 复赛真题及答案解析（最新更新）
• 2025 csp-x(山东) 复赛真题及答案解析（最新更新）
• 2025 csp-x(河南) 复赛真题及答案解析（最新更新）
• 2025 csp-x(辽宁) 复赛真题及答案解析（最新更新）
• 2025 csp-x(江西) 复赛真题及答案解析（最新更新）
• 2025 csp-x(广西) 复赛真题及答案解析（最新更新）
• 2020 ~ 2024 csp 复赛真题题单及题解
• 2019 ~ 2022 csp-j 初赛高频考点真题分类解析
• 2021 ~ 2024 csp-s 初赛高频考点解析
• 2023 ~ 2024 csp-x (山东)初赛真题及答案解析
• 2024 csp-j 初赛真题及答案解析
• 2025 csp-j 初赛真题及答案解析（最新更新）
• 2025 csp-s 初赛真题及答案解析（最新更新）
• 2025 csp-x (山东)初赛真题及答案解析(最新更新)
• 2025 csp-x (江西)初赛真题及答案解析(最新更新)
• 2025 csp-x (辽宁)初赛真题及答案解析(最新更新)

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

• 129 道刷题练习和详细题解，涉及：模拟算法、数学思维、二分算法、 前缀和、差分、深搜、广搜、DP专题、 树和图

4、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}