Leetcode 1547: minimum cost of cutting sticks

subject

There's a length of n A unit of wooden stick , Stick from 0 To n Several positions are marked . for example , The length is 6 The stick can be marked as follows ：

Give you an array of integers cuts , among cuts[i] Indicates where you need to cut the stick .
You can finish cutting in order , You can also change the cutting order as needed .
The cost of each cut is the length of the stick currently to be cut , The total cost of cutting the stick is the sum of all previous cutting costs . Cutting a stick will divide a stick into two smaller sticks （ The sum of the length of these two sticks is the length of the stick before cutting ）. See the first example for a more intuitive explanation .
Return to the of cutting the stick Minimum total cost .

Example

Example 1

Input ：n = 7, cuts = [1,3,4,5]
Output ：16
explain ：
Press [1, 3, 4, 5] The sequence of cutting is as follows ：

The first cut length is 7 My stick , Cost is 7 . The second cutting length is 6 My stick （ That is, the second stick obtained from the first cutting ）, The third cut is the length 4 My stick , The final cutting length is 3 My stick . The total cost is 7 + 6 + 4 + 3 = 20 .
And rearrange the cutting sequence to [3, 5, 1, 4] after ,

The total cost = 16（ As shown in the example figure 7 + 4 + 3 + 2 = 16）.

Example 2

Input ：n = 9, cuts = [5,6,1,4,2]
Output ：22
explain ： If you cut in a given order , Then the total cost is 25 . The total cost <= 25 There are many cutting sequences , for example ,[4,6,5,2,1] The total cost of = 22, It is the least cost of all possible solutions .

2 <= n <= 10^6
1 <= cuts.length <= min(n - 1, 100)
1 <= cuts[i] <= n - 1
cuts All integers in the array are Different from each other

Code

Ideas ：

• Put the two ends of the stick （0 and n） Add to cuts The array becomes newCuts Array , And arrange them in ascending order ,dp[l][r] It means that the first part of this wooden stick l To the first r The minimum cost of cutting at one cutting point (l and r by newCuts Index of the array ）.
• Every time I want to i To the first j This piece of wood with two cutting points （ That is, in the interval ） Cut into two （ There may be cutting points to cut in each ）, And the lowest cost . So it can be reversed , Such as the first dp Get the minimum cost of cutting every three consecutive cutting points into two parts , Then you can use the former information ,dp Calculate the minimum cost of cutting every four consecutive points into two parts …

1. When r=l+1, That is, two adjacent cutting points , There is only one section in its own interval , Therefore, there is no need to cut , Cost is 0;
2. When r>l+1 when , stay （l,r） Intermediate cutting point k, That is to say k Cut off at , The cost of cutting is interval length newCuts[r] - newCuts[l];
3. So... In the interval （ That is to say l To the first r One cutting point completes the cutting ） The minimum cost conversion equation is ：dp[l][r] = min {dp[l][k]+dp[k][r]+cuts[r]-cuts[l]}, among k∈(l, r) Integer of open interval .

class Solution {
    
    public int minCost(int n, int[] cuts) {
    
        int[] newCuts = new int[cuts.length + 2];
        newCuts[0] = 0;
        for(int i=0;i<cuts.length;i++){
    
            newCuts[i+1] = cuts[i];
        }
        newCuts[cuts.length + 1] = n;
        Arrays.sort(newCuts);
        int[][] dp = new int[newCuts.length][newCuts.length];
        // Enumeration interval ,len Indicates the interval length 
        for(int len=2;len<newCuts.length;len++){
    
            // Enumerate the left end of the interval 
            for(int i=0;i+len<newCuts.length;i++){
    
                //j Is the right end of the interval 
                int j = i + len;
                dp[i][j] = Integer.MAX_VALUE;
                // Enumerate the partition points of the interval 
                for(int k=i+1;k<j;k++){
    
                    dp[i][j] = Math.min(dp[i][j],dp[i][k]+dp[k][j]+newCuts[j]-newCuts[i]);
                }
            }
        }
        return dp[0][newCuts.length-1];

    }
}

LeetCode 1547. The minimum cost of cutting a stick