PS：
好久没写过算法题了，如果发现错误还望大佬指出，
超级胶水
小明有n颗石子，按顺序摆成一排，他准备用胶水将这些石子黏在一起。
梅克什字有自己的重量，如果将两颗石子黏在一起，重量就是两个石子重量之和
为了粘贴牢固，该题认为两个石子粘连需要的胶水为两个石子的重量乘积。
每次只能合并相邻的两颗石子，并将合成的石子放在原来的位置，用最少的交水黏在一起，
请帮助小明计算最少需要多少胶水
输入：
n：石子的数量
n个整数w1，w2……wn，表示每颗石子的重量
输出：
最少的胶水数量
package 第十一届蓝桥杯; import java.util.Scanner; public class 超级胶水 { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[] a = new int[1010]; int[][] dp = new int[1010][1010]; int[][] jiaoshui = new int[1010][1010]; //dp[i][j]代表从第i个到第j个石头合并的重量 //jiaoshui[i][j]代表从第i个到第j个石头合并的胶水量 for (int i=1; i<=n; i++) { a[i] = in.nextInt(); dp[i][i]=a[i]; } // for (int i=1; i<n; i++) { // for(int j=i+1; j<=n; j++) { // dp[i][j]=dp[i][j-1]+a[i]; // } // } //r是循环的范围，要从两个石头合并开始算，因为只有相邻的才能合并 for (int r=2; r<=n; r++) { //循环起始点，j就是从i向后r个范围的点j for (int i=1; i<=n-r+1; i++) { int j=i+r-1; jiaoshui[i][j] = Integer.MAX_VALUE; //这个是代表的用的哪个范围合并的石头，最后要加起来 int temp1 = 0; //这个是取两个相邻石头差值最大的拼凑 // 好比一共10个石头 // 差值小：一堆分五块 5*5=25 // 差值大： 一个1块一个9块 1*9=9 //胶水量形成了鲜明的对比，差值大的省胶水 int tempmax = -1; for (int k=i; k<j; k++) { if(tempmax< Math.abs(dp[i][k] - dp[k+1][j])){ //保存从哪里分开（哪两堆石头合并起来的） temp1=k; //dp[i][j]代表从第i个到第j个石头合并有重 dp[i][j] = dp[i][k] + dp[k+1][j]; //找差值最大的进行合并省胶水 tempmax=Math.abs(dp[i][k] - dp[k+1][j]); jiaoshui[i][j] = dp[i][k] * dp[k+1][j]; } } //如果jiaoshui[i][i]表示的是一个石头，一个石头粘连在一起是不需要胶水的，这里要跳过 if(i!=temp1) jiaoshui[i][j]+=jiaoshui[i][temp1]; if(temp1+1!=j) jiaoshui[i][j]+=jiaoshui[temp1+1][j]; } } //1-n粘连需要的最小胶水 System.out.println(jiaoshui[1][n]); } }