Analysis of stone merging

282. Stone merging

 Equipped with  N  Pile stones in a row , Its number is  1,2,3,…,N.

 Every pile of stones has a certain quality , It can be described as an integer , Now we're going to put this  N  The stones are combined into a pile .

 Only two adjacent stacks can be merged at a time , The price of the merger is the sum of the masses of the two piles of stones , After merging, the stones adjacent to the two piles will be adjacent to the new pile , Because the order of selection is different when merging , The total cost of the merger is also different .

 For example, there are  4  The heaps of stones are  1 3 5 2,  We can merge first  1、2  Pile up , The cost is  4, obtain  4 5 2,  Merge again  1,2  Pile up , The cost is  9, obtain  9 2 , And then merge to get  11, The total cost is  4+9+11=24;

 If the second step is to merge first  2,3  Pile up , The price is  7, obtain  4 7, The cost of the last merger is  11, The total cost is  4+7+11=22.

 The problem is ： Find a reasonable way , Minimize the total cost , The minimum cost of output .

 Input format 
 Number one on the first line  N  Represents the number of piles of stones  N.

 The second line  N  Number , Represents the mass of each pile of stones ( Not more than  1000).

 Output format 
 Output an integer , The minimum cost .

 Data range 
1≤N≤300
 sample input ：
4
1 3 5 2
 sample output ：
22

Method 1： Section DP

• Section DP The classic question of ,$f[i][j]$ Express the $[i...j]$ The minimum cost of merging stones into a pile
• Dynamic transfer equation
  • $f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+sum[i...j])$

class Main {
    
    public static void main(String[] args) {
    
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] stones = new int[n];
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) {
    
            stones[i - 1] = in.nextInt();
            sum[i] = sum[i - 1] + stones[i - 1];
        }
        int[][] f = 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;
                f[i][j] = Integer.MAX_VALUE;
                for (int k = i; k < j; k++) {
    
                    f[i][j] = Math.min(f[i][j], f[i][k] + f[k + 1][j] + sum[j] - sum[i - 1]);
                }
            }
        }
        System.out.println(f[1][n]);
    }