有nn堆石子排成一列，每堆石子有一个重量wiw_i, 每次合并可以合并相邻的两堆石子，一次合并的代价为两堆石子的重量和wi+wi+1w_i+w_{i+1}，求怎样合并能使合并代价最小，输出最小代价。

题解

区间DP

记合并[l,r][l,r]这段区间内的石子所需的代价为f(l,r)f(l,r)，则有:

f(l,r)=mink=lr−1(f(l,r), f(l,k)+f(k+1,r))+sum(l,r) f(l,r)=\min_{k=l}^{r-1}(f(l,r),\ f(l,k) + f(k+1,r))+sum(l,r)

记sum(l,r)=∑i=lrwisum(l,r)=\sum\limits_{i=l}^{r}w_i

那么接下来的工作就是确定递推顺序，这题的递推顺序是从短区间向长区间递推，因为我们发现状态中每次转移需要用到的状态只需要用到从之前的较短的区间中得到的值。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
using namespace std;
const int MAXN = 100;
int a[MAXN + 1], f[MAXN + 1][MAXN + 1];
int main () {
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        a[i] = a[i] + a[i - 1];
    }
    for (int i = 1; i <= n; i++) f[i][i] = 0;
    for (int len = 1; len < n; len++) {
        int r;
        for (int l = 1; l <= n - len; l++) {
            r = l + len;
            int minn = INT_MAX;
            for (int k = l; k < r; k++) {
                minn = min(f[l][k] + f[k + 1][r], minn);
            }
            f[l][r] = minn + a[r] - a[l - 1];
        }
    }
    printf("%d\n", f[1][n]);
    
    return 0;
}