90分超時

import java.util.Scanner;public class Main {		public static void main(String[] args) {		Scanner in = new Scanner(System.in);		int n = in.nextInt();		int[] a = new int[1010];		int[][] temp = new int[1010][1010];		int[][] dp = new int[1010][1010];		for(int i=1; i<=n; i++) {			a[i] = in.nextInt();			temp[i][i] = a[i];		}		for(int i=1; i<n; i++) {			for(int j=i+1; j<=n; j++) {				temp[i][j] = temp[i][j-1] + a[j];			}		}		for(int r=2; r<=n; r++) {			for(int i=1; i<=n-r+1; i++) {				int j=i+r-1;				dp[i][j] = Integer.MAX_VALUE;				for(int k=i; k<j; k++) {					if(dp[i][j] > dp[i][k] + dp[k+1][j])						dp[i][j] = dp[i][k] + dp[k+1][j];				}				dp[i][j] += temp[i][j];			}		}		System.out.PRintln(dp[1][n]); 	}}