1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
| import java.util.*; class Main{ static int[] arr; static int[] s; static int n ; public static void main(String[] args){ Scanner sc = new Scanner(System.in); n = sc.nextInt(); arr = new int[n]; for(int i = 0; i < n; i++){ arr[i] = sc.nextInt(); } s = new int[n+1]; System.out.println(getCost()); } public static int getCost(){ for(int i = 1; i <= n; i++){ s[i] = s[i-1] + arr[i-1]; } int[][] dp = new int[n+1][n+1]; for(int l = 1; l < n; l++){ for(int i = 1; i + l <= n; i++){ int j = i + l; dp[i][j] = 100000000; 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]); } } } return dp[1][n]; } }
|