【例9.18】合并石子（信息学奥赛一本通- P1274）从暴搜到区间 DP：石子合并的四种写法-洪萨配资

【题目描述】

在一个操场上一排地摆放着Ｎ堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的２堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

计算出将Ｎ堆石子合并成一堆的最小得分。

【输入】

第一行为一个正整数N (2≤Ｎ≤100)；

以下Ｎ行,每行一个正整数，小于10000，分别表示第i堆石子的个数(1≤i≤N)。

【输出】

一个正整数，即最小得分。

【输入样例】

7 13 7 8 16 21 4 18

【输出样例】

在信息学奥赛中，区间动态规划是一座必须翻越的大山。很多同学理解“状态转移方程”不难，但一到写代码，经常i, j, k三层循环绕晕。

今天我们以最经典的“石子合并”为例，通过四种写法的演变，彻底搞懂暴搜到标准 DP 模板的思维转变。

0. 题目回顾

题目描述：有N堆石子排成一排，每次只能合并相邻的两堆，代价为两堆石子总数。求将所有石子合并成一堆的最小代价。

数据范围：（这暗示我们需要一个O(N^3)的算法）。

1. 朴素递归

拿到这个问题，我们的第一直觉通常是倒推：

“要合成一大堆，最后一步一定是把‘左边一堆’和‘右边一堆’合并起来。”

既然不知道在哪里切分，那就枚举所有可能的切分点k。这就有了我们第一版的代码。

代码版本 1.0：纯递归（TLE）

//石子合并未记忆化 #include <iostream> using namespace std; int a[110];//记录原来第i堆石头有多少颗 int s[110];//前缀和数组 int rangecom(int l,int r){ if(l==r) return 0;//如果只有一堆石子了，合并不需要代价 int ans=0x3f3f3f3f;//最小总代价 for(int i=l;i<r;i++){//枚举分界线i //找出合并产生左半堆（l-i)和合并产生右半堆(i+1-r)的最小总代价 ans=min(ans,rangecom(l,i)+rangecom(i+1,r)); } //最后合并左右两堆，总代价还要加上合并左半堆和右半堆的代价（即l-r的石子总数 前缀和算出） return ans+s[r]-s[l-1]; } int main() { int n; cin>>n; //记录原来第i堆石头有多少颗 for(int i=1;i<=n;i++) cin>>a[i]; //对石子做前缀和 for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i]; cout<<rangecom(1,n);//1-n堆石子合并总代价 return 0; }

总结：

逻辑：完全正确，体现了区间DP的“最优子结构”性质。
问题：重复计算太严重了，比如rangecom(1, 2)这个小区间，会在计算rangecom(1, 3)、rangecom(1, 4)等大区间时被反复调用成千上万次。
结果：指数级复杂度O(2^N)，提交即超时。

2. 加上记忆化搜索

为了解决超时，我们只需要准备一个数组f[][]。每次算出一个区间的答案，先记下来；下次遇到同样的区间，直接查表，不用再算。

代码版本 2.0：记忆化搜索（推荐初学者）

这是自顶向下的经典写法，逻辑最符合人类思维。

//石子合并记忆化 #include <iostream> #include <cstring>//对应memset using namespace std; int a[110];//记录原来第i堆石头有多少颗 int s[110];//前缀和数组 int f[110][110];//f[i][j]代表合并i-j堆石子的最小总代价 int rangecom(int l,int r){ if(f[l][r]!=-1) return f[l][r]; if(l==r) return f[l][r]=0;//如果只有一堆石子了，合并不需要代价 int ans=0x3f3f3f3f;//最小总代价 for(int i=l;i<r;i++){//枚举分界线i //找出合并产生左半堆（l-i)和合并产生右半堆(i+1-r)的最小总代价 ans=min(ans,rangecom(l,i)+rangecom(i+1,r)); } //最后合并左右两堆，总代价还要加上合并左半堆和右半堆的代价（即l-r的石子总数 前缀和算出） return f[l][r]=ans+s[r]-s[l-1]; } int main() { int n; cin>>n; //初始化f数组为-1，不能为0 因为记忆化搜索的初始化值，必须是一个绝对不可能在计算过程中出现的数值，这样才能用来标记“未访问” memset(f,-1,sizeof(f)); //记录原来第i堆石头有多少颗 for(int i=1;i<=n;i++) cin>>a[i]; //对石子做前缀和 for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i]; cout<<rangecom(1,n);//1-n堆石子合并总代价 return 0; }

总结：

初始化：一定要用-1初始化，避免与代价0混淆。
适用场景：适合逻辑复杂的 DP 题，或者状态比较稀疏的情况。

3. 进阶：动态规划

记忆化搜索是“倒着求”，而动态规划是“正着推”。我们从小区间开始，慢慢填满一张表。

在写循环版本时，有两种主流的循环风格。

代码版本 3.0：枚举“区间跨度”（Gap写法）

有些同学喜欢用第一层循环变量i表示区间长度减1（即左右端点的距离 gap）。

//石子合并动态规划写法 #include <iostream> #include <cstring>//对应memset using namespace std; int a[110];//每一堆石子有多少颗 int s[110];//前缀和数组 int dp[110][110];//dp[i][j]为合并第i--j堆石子所需的最小总代价 int main(){ int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; //求前缀和 for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i]; memset(dp,0x3f,sizeof(dp));//初始化dp数组为无穷大 for(int i=1;i<=n;i++) dp[i][i]=0;//自己合并自己代价为0 for(int i=1;i<=n;i++){//遍历区间大小（右端点减去左端点的值）从1-n for(int j=1;j<=n-i;j++){//j为左端点 for(int k=j;k<i+j;k++){//k为分界线 分界线大于等于左端点 小于右端点 dp[j][j+i]=min(dp[j][j+i],dp[j][k]+dp[k+1][j+i]+s[j+i]-s[j-1]); } } } cout<<dp[1][n]; return 0; }

总结：

这种写法完全正确，但i代表gap在理解上稍微有点“绕”，容易在考场紧张时搞错边界。

4. 终极形态：标准区间DP模板

为了让逻辑更加清晰，也为了方便后续学习（如四边形不等式优化），我们推荐使用“枚举长度”作为第一层循环的标准写法。

核心口诀：

先枚举长度len（从小到大，地基打好才能盖楼）
再枚举起点i（推算终点j）
最后枚举分割点k（决策最优解）

代码版本4.0：标准模板

//石子合并动态规划写法优化 竞赛通用标准模板 #include <iostream> #include <cstring>//对应memset using namespace std; int a[110];//每一堆石子有多少颗 int s[110];//前缀和数组 int dp[110][110];//dp[i][j]为合并第i--j堆石子所需的最小总代价 int main(){ int n; cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; //求前缀和 for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i]; memset(dp,0x3f,sizeof(dp));//初始化dp数组为无穷大 for(int i=1;i<=n;i++) dp[i][i]=0;//自己合并自己代价为0 //第一层循环枚举：区间长度len (从2到n) for(int len=2;len<=n;len++) { //第二层循环枚举：左端点i (确保 i+len-1不越界) for(int i=1;i+len-1<=n;i++) { int j=i+len-1;//算出右端点j //第三层循环枚举：分割点k(从i到j-1) for(int k=i;k<j;k++) { dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1]); } } } cout<<dp[1][n]; return 0; }

总结：