【区间DP模板】

解题思路:

将n堆石子合并成一堆且每次只能合并相邻的两堆，

所以第n-1即最后一次合并肯定是由两堆变一堆

假设两堆的区间长度分别为[1,x][x+1,n]

而对那两堆的每一堆而言肯定是由更小的两堆合并过来的

即[1,x]肯定是由[1,a][a+1,x]合并来的，[x+1,n]是由[x+1,b],[b+1,n]合并来的

不断往前推发现，区间的长度在不断变小，那么区间的边界情况是什么？

当然是区间长度为1时，因为 此时的区间长度达到最小，不可能更小了，对于区间[a,a]而言，只包括了一堆石子，此时无法进行合并，故消耗代价为0

而DP的过程又是递推的过程，关键是找到递推的公式和边界

对于此题，我既然已经知道最大的区间答案是由小区间推过来的，那我只要保证小区间的和最优即保证了大区间的结果最优

递推公式：dp[l][r]=min[dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1])

递推边界：dp[i][i]=0 

对于dp[i][j]的理解：i-j区间的所有石子合并为一堆消耗的最小代价

我们求得答案是dp[1][n]即区间1-5所有石子合并成一堆消耗的最小代价

注意事项:

参考代码:

import java.io.*;
import java.util.*;
 
  public class Main{
      static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
      static PrintWriter pw =new PrintWriter(new OutputStreamWriter(System.out));
      public static void main(String[]args) throws IOException{
          int n=Integer.parseInt(br.readLine());
          int []arr=new int[n+1];
          long []sum=new long [n+1];
          long [][]dp=new long[n+1][n+1];
          String []s=br.readLine().split(" ");
        for(int i=1;i<=n;i++){
            Arrays.fill(dp[i],Long.MAX_VALUE);//初始化正无穷
        }
          for(int i=1;i<=n;i++){
              arr[i]=Integer.parseInt(s[i-1]);
              sum[i]=sum[i-1]+arr[i];//前缀和 
              dp[i][i]=0;
          }
          //区间DP模板 三层for
          for(int len=2;len<=n;len++){   //阶段：枚举区间长度
              for(int l=1;l+len-1<=n;l++){//状态：枚举区间起点
                  int r=len+l-1;//区间终点
                  for(int k=l;k<r;k++){  //决策：枚举分割点
                      dp[l][r]=Math.min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]);
                   }
              }
          }
          pw.println(dp[1][n]);
          pw.flush();
      }
  }