前言：

今日之所学区间dp，归一总结

概述：

所谓区间dp，指在一段区间上进行动态规划，一般做法是由长度较小的区间往长度较大的区间进行递推，最终得到整个区间的答案，而边界就是长度为1以及2的区间。
区间dp常见的转移方程如下：

1
dp(i,j) = min{dp(i,k-1) + dp(k,j)} + w(i,j)   (i < k <= j)

实践

题目：石子合并

在一个操场摆放 N堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的 2 堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。试设计出一个算法,计算出将 N堆石子合并成 1堆的最小得分

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int dp[N][N],s[N];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){cin>>s[i];s[i]+=s[i-1];}
    for(int len=2;len<=n;len++)
        for(int i=1;len+i-1<=n;i++)
        {
            int l=i;
            int r=len+l-1;
            dp[l][r]=1e6;
            for(int k=l;k<r;k++)
                dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+s[r]-s[l-1]);
        }
    cout<<dp[1][n];
    return 0;
}