题目：有n堆石子排成一列，每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子，一次合并的代价为两堆石子的重量
和w[i]+w[i+1]。问安排怎样的合并顺序，能够使得总合并代价达到最小。
输入：
第一行一个整数n(n<=100)
第二行n个整数w1,w2...wn (wi <= 100)
输出：一个整数表示最小合并代价
这是一个比较经典的动态规划问题，对于给定的石子，当合并完后，只会剩余一堆石子，而这一堆石子是由两堆石子合并而来的。
通过倒推可以知道，第i~j堆已合并石子可以由i~k堆已合并石子与k~j堆已合并石子合并而来(i<=k<=j)。即dp[i][j]=dp[i][k]+dp[k][j]
+sum[i][j];(sum[i][j]为这堆石子的合并代价)
于是可以有
for(j=1;j<=n;j++)
{for(i=j-1;i>0;i--)
{
dp[i][j]=dp[i][i]+dp[i+1][j]+sum[i][j];for(k=i+1;k
{
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[i][j]);
}
}
}
其中dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[i][j]);是找出第i~j堆石子合并的的最小带价。下面是全代码：
#include#include
using namespacestd;int min(int a,int b)//找出a,b的最小值。
{if(a>b) returnb;else returna;
}intmain()
{int sum[101][101],dp[101][101],w[101];
memset(sum,0,sizeof(sum));
memset(dp,0,sizeof(dp));intn,i,j,k;
cin>>n;for(i=1;i<=n;i++)//读入每个石子堆对应的代价。
{
cin>>w[i];
}for(i=1;i<=n;i++)//计算从i到j的石子堆的总代价，用sum[i][j]表示。
{
sum[i][i]=w[i];for(j=i+1;j<=n;j++)
{
sum[i][j]=sum[i][j-1]+w[j];
}
}for(j=1;j<=n;j++)//通过动态规划找出最优的代价。
{for(i=j-1;i>0;i--)
{
dp[i][j]=dp[i][i]+dp[i+1][j]+sum[i][j];for(k=i+1;k
{
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[i][j]);//dp[i][k]，dp[k+1][j]表示合成这堆石子//的前两堆石子的合并的最小代价。
}
}
}
cout<
}
实例：
输入：4
4 1 1 4
输出：18
程序分析：sum[1][1]=4,sum[1][2]=5,sum[1][3]=6,sum[1][4]=10,
sum[2][2]=1,sum[2][3]=2,sum[2][4]=6,...
dp[1][2]=5,dp[2][3]=2,dp[1][3]=8.
dp[1][2]+dp[2][3]+sum[1][3]=13
dp[1][3]=min(dp[1][3],dp[1][2]+dp[2][3]+sum[1][3])=8;
...
最后可得结果为 18，
