石子合并 动态规划 java_动态规划：圆形石子合并问题
问题描述：
在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。
规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
试设计一个算法，计算出将n堆石子合并成一堆的最小得分。
import java.util.Scanner;
public class Test {
/*
* 圆形石子问题动态规划解法。
* p[i] 表示第i堆石子的个数。
* sum[i][j] 表示从第i堆石子开始，长度为j的各堆石子的总分。
* dp[i][j] 表示从第i堆石子开始，长度为j的各堆石子的最优组合的分数，即分数最小。
* 其中dp[i][1]=0;
* dp[i][j]=min(dp[i][k]+dp[(i+k-1)%n+1][j-k]+sum[i][j]),其中1<=k
*/
public static void main(String[] args){
Scanner reader = new Scanner(System.in);
int n = reader.nextInt();
int[] p = new int[n+1];
int[][] sum = new int[n+1][n+1];
int[][] dp = new int[n+1][n+1];
for(int i=1;i<=n;i++){
p[i] = reader.nextInt();//初始化每堆石子的个数
}
/**
* 初始化sum
*/
for(int i=1;i<=n;i++){
sum[i][1] = p[i];//长度为1
}
for(int j=2;j<=n;j++){
for(int i=1;i<=n;i++){
sum[i][j] = sum[i][j-1]+p[(i+j-2)%n+1];//从i开始，长度为j的石子的总数为从i开始长度为j-1的石子总数加上最后一堆石子数
}
}
/**
* 初始化dp
*/
for(int i=1;i<=n;i++){
dp[i][1] = 0;//长度为1的组合分数为0
}
for(int j=2;j<=n;j++){
for(int i=1;i<=n;i++){
dp[i][j] = Integer.MAX_VALUE;
for(int k=1;k
int temp = dp[i][k]+dp[(i+k-1)%n+1][j-k]+sum[i][j];//通过子结构求dp，长度k为划分点，在1到j之间，不包括k
dp[i][j] = Math.min(temp, dp[i][j]);
}
}
}
int minScore = dp[1][n];
for(int i=2;i<=n;i++){
minScore = Math.min(minScore, dp[i][n]);//得分最小的组合一定是从i开始，长度为n的组合，找到最小的一个组合
}
System.out.println("MINSCORE:"+minScore);
}
}