地址：https://www.acwing.com/problem/content/284/
题意：给一堆石子，相邻的合并，问最后得到的最小花费，花费具体算法在题里。
解析：
对于此题，根据常识，对于最终状态，是由两团合并的。所以定义dp[i][j]表示区间i-j合并的最小值。
二堆合并：dp[1][2]=dp[1][1]+dp[2][2]+sum[1~2];
即dp[i][i+1]=dp[i][i]+dp[i+1][i+1]+sum[i~i+1];
三堆合并：dp[1][3]=min(dp[1][1]+dp[2][3],dp[1][2]+dp[3][3])+sum[1~3];
dp[i][i+2]=min(dp[i][i]+dp[i+1][i+2],dp[i][i+1]+dp[i+2][i+2])+sum[i~i+2];
综上推广到第i堆到第j堆的合并，dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
三个for,相当于遍历每一个长度的区间。
感觉有点floyed 的意思.....找中转点
#include<iostream> #include<cstdio> #include<cstring> const int maxn = 500; const int inf = 1e9; int dp[maxn][maxn]; int a[maxn],sum[maxn]; using namespace std; int main() { int n; cin>>n; sum[0]=0; for(int i = 1;i <= n ; i++) { cin>>a[i]; sum[i]=sum[i-1]+a[i]; } for(int len =2 ; len <= n ;len++) { for(int l = 1; l+len-1<=n; l++) { int r=l+len-1; dp[l][r]=inf; for(int k = l ; k < r ; k ++) { dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]); } } } cout<<dp[1][n]<<endl; }
原文：https://www.cnblogs.com/liyexin/p/12683151.html