问题描述
在一条直线上有n堆石子，每堆有一定的数量，每次可以将两堆相邻的石子合并，合并后放在两堆的中间位置，合并的费用为两堆石子的总数。求把所有石子合并成一堆的最小花费。
输入格式
输入第一行包含一个整数n，表示石子的堆数。
接下来一行，包含n个整数，按顺序给出每堆石子的大小 。
输出格式
输出一个整数，表示合并的最小花费。
样例输入
5
1 2 3 4 5
样例输出
33
数据规模和约定
1<=n<=1000, 每堆石子至少1颗，最多10000颗。
这道题和矩阵乘法有些相似，状态和状态转移都有些差不多，这道题简单一点。我们设一个sum（i，j）函数求索引i到j的石子的和
设d（i，j）为最把i到j的石子合并的最小花费
状态量。我们可以知道当我们进行最后一步合并时，只剩下两堆石子，此时合并石子的花费就是sum（1，n），只不过他的的子堆的合并花费可能不同，需要去比较得出最小的。
状态转移方程：d(i,j)=min{d(i,t)+d(t+1,j)+sum(i,j)|t大于等于i小于j}
代码：
import java.util.Scanner;
public class Main
{
static int dp[][];
static int a[];
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
dp=new int[n+1][n+1];
a=new int[n+1];
for(int i=1;i<=n;i++)
a[i]=sc.nextInt();//存储每个石子
System.out.println(find(1,n));
}
static int find(int l,int r)//递归寻找
{
if(dp[l][r]!=0)return dp[l][r];//记忆化
if(l==r)return 0;//石子本身必须要有花费
if(l+1==r)return dp[l][r]=a[l]+a[r];//这一步可不需要
dp[l][r]=Integer.MAX_VALUE;
int sum=ca(l,r);//计算l（left）到r（right）的石子和
for(int i=l;i<r;i++)
{
dp[l][r]=Math.min(dp[l][r], find(l,i)+find(i+1,r)+sum);//不断去逼近最小值
}
return dp[l][r];
}
static int ca(int l,int r)
{
int sum=0;
for(int i=l;i<=r;i++)
sum+=a[i];
return sum;
}
}这段代码在蓝桥杯上提交以后值得了90，最后一组测试超时（一共10组），分析了一下一定ca这个这个计算函数的多次计算超时了，后来发现在已知一个序列，然后多次询问某个区间和，这个是线段树啊，打算用线段树来实现ca这个函数功能，但是突然想起一个远古代码（真的突然想起来。。。）然后做了如下修改
import java.util.Scanner;
public class Main
{
static int dp[][];
static int sum[];//增设一个数组，如sum[n]等于1到n的所有石子和
static int a[];
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
dp=new int[n+1][n+1];
a=new int[n+1];
sum=new int[n+1];
for(int i=1;i<=n;i++)
{
a[i]=sc.nextInt();
sum[i]=a[i]+sum[i-1];//巧妙就在于这，sum[i]是递推得到的
}
System.out.println(find(1,n));
}
static int find(int l,int r)
{
if(dp[l][r]!=0)return dp[l][r];
if(l==r)return 0;
if(l+1==r)return dp[l][r]=a[l]+a[r];
dp[l][r]=Integer.MAX_VALUE;
int s=sum[r]-sum[l-1];//那么计算r到l的和就只有常数时间
for(int i=l;i<r;i++)
{
dp[l][r]=Math.min(dp[l][r], find(l,i)+find(i+1,r)+s);
}
return dp[l][r];
}
}10组全部通过了 效率还比线段树高一点，汗。。。
但是适用条件是原始数据必须得是静态的，如果有被动态的修改过，那就只能用线段树或者树状数组。