java 代码

import java.util.Scanner;
import java.lang.Integer;

class Main{

        public static void main(String[] args){

            // 读取数据的代码
            Scanner reader = new Scanner(System.in);
            int N = reader.nextInt();
            int[] s = new int[N + 1];               // 前i项的和
            for(int i = 1; i <= N; i++){
                s[i] = reader.nextInt();
                s[i] += s[i - 1];
            }

            reader.close();

            int[][] dp = new int[N + 1][N + 1];
            for(int len = 2; len <= N; len++){                      // 先遍历长度
                for(int i = 1; i + len - 1 <= N; i++){              // 再遍历左边的游标

                    int j = i + len - 1;
                    dp[i][j] = Integer.MAX_VALUE;
                    for(int k = i; k < j; k++)                         // 最后遍历右边的游标
                    {
                        dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + s[j] - s[i - 1]);
                    }
                }
            }
            System.out.println(dp[1][N]);
        }
}