石堆合并问题

问题：在一条直线上有n堆石子，每堆有一定的数量，每次可以将两堆相邻的石子合并，合并后放在两堆的中间位置，合并的费用为两堆石子的总数。求把所有石子合并成一堆的最小花费。

状态：

1、dp[i][j]=0 (i==j)

2、dp[i][j]=min(dp[i][k]+dp[k][j])+sum[i][j] (i!=j)

static int dp(int i,int j,int[] sum,int[][] dp){
if(dp[i][j]==Integer.MAX_VALUE){
for(int k=i;k<j;k++){
dp[i][j]=Math.min(dp[i][j],dp(i,k,sum,dp)+dp(k+1,j,sum,dp)+sum[j]-sum[i-1]);
}
}
return dp[i][j];
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] sum = new int[n+1];
int[][] dp = new int[n+1][n+1];
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+in.nextInt();
Arrays.fill(dp[i],Integer.MAX_VALUE);
dp[i][i]=0;
}
dp(1,n,sum,dp);
System.out.println(dp[1][n]);
}

最后

以上就是安静苗条为你收集整理的石堆合并问题的全部内容，希望文章能够帮你解决石堆合并问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。