[leetcode] dynamic programming solution partition array i[red fox]

Welcome to 、 give the thumbs-up 、 forward 、 subscribe , Between your hands , My power source .

Write this question , From an official description I saw "「 Split the array into m paragraph , seek ……」 Dynamic programming is a common question .", It reminds me of what I wrote before 1043. Separate the arrays to get the maximum and , An early solution to the problem , Style is more like a draft , However, there are still many friends who like to read and praise , Thank you thank you , Refill ~

Define the State

$dp[i][j]$ Before presentation $i$ The number is $nums[0...i-1]$ The number between is divided into $j$ paragraph , Made up of $j$ The smallest of the maximum values of the respective sums of the subarrays

Transfer equation

Think about the class of dynamic programming , A bit like Taoism Dao begets One , One begets Two , Two begets Three , Our vision-be , From special cases to general cases , Deductive induction

Back to this topic, the same is true , The goal is to seek $dp[i][j]$, Read this definition again ： Before presentation $i$ The number is $nums[0...i-1]$ The number between is divided into $j$ paragraph , Made up of $j$ The smallest of the maximum values of the respective sums of the subarrays , Can we ask him to be here $nums[0...i-1]$ Try using scissors , Subtract both ends , Consider in two parts ？

• The second paragraph ： It can be imagined as the $j$ paragraph , As shown in the picture $nums[k,k+1,....i-1]$, Because we take the former $i$ Number , Array index from $0$ At the beginning , The sum of this part is obviously $sum(nums[k,k+1,...i-1])$

• The first paragraph ： It can be imagined as before $j-1$ paragraph , What about this paragraph ？ Since it is $j-1$ paragraph , Actually sum $j$ There's no big difference between paragraphs , It can be transformed into $dp$, That is to say $dp[k][j-1]$, Before presentation $k$ The number is $nums[0...k-1]$ The number between is divided into $j-1$ paragraph , Made up of $j-1$ The minimum value of the maximum value of the respective sum of the subarrays

• The minimum value at the top two ends is $dp[i][j]$ Result , namely $dp[i][j]$= $max$($dp[k][j-1]$,$sum[k...i-1]$), Then this is just one of them , That is to say $k$ There are many possibilities ,$k$ The range can be from $0$ Fetch $i-1$, exceed $i-1$ It makes no sense , If $k$>$i-1$, Before presentation $k$ Number , But the goal only considers the former $i$ Number

• The final transfer equation ：

  ​ $dp[i][j]$=$min$[$max$($dp[k][j-1],sum[k...i-1]$)] , among 0=<$k$<=$i-1$

The border

• $dp[0][0]$ Before presentation 0 The number is divided into 0 paragraph , This makes no logical sense , How does this happen , That is the whole $nums[0...i-1]$ Is divided into $j=1$ paragraph , that $dp[k][j-1]$ It becomes $dp[0][0]$, Take the same as $sum[k...i-1]$ The maximum of , As long as you make $dp[0][0]$=0 Will not affect the final result
• $j$>$i$, It makes no sense , because , front $i$ Numbers cannot be divided into more than $i$ paragraph , Because a number can only be divided into one group at most , If each array is a separate group , That is to say $i$ Group , Can not tell greater than $i$ Group situation , In the process of variable traversal ,$j$ The value of should be $min(m,i)$,$m$ Is the upper limit of the number of partitions given in the title
• The outermost $min$ If the initial value is 0, Will affect the results , Set up a $MAX$ value , Every time the

Prefixes and auxiliary arrays

Definition $prefix[i]$ Express $nums$ Before array $i$ The number and , namely $nums[0...i-1]$ Before and , This prefix and array initialization $n+1$,$prefix[0]$ redundancy , Most auxiliary array

Take the example in the figure , Printed $dp$ as follows

[[0,MAX,MAX],
[MAX,7,MAX],
[MAX,9,7],
[MAX,14,7],
[MAX,24,14],
[MAX,32,18]]

A small function

• Fill in a two-dimensional array , Traversal line , Fill each column

        for (int i = 0; i <= n; i++) {
    
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }

Complete code

    public int splitArray(int[] nums, int m) {
    
        int n = nums.length;
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
    
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) {
    
            prefix[i + 1] = nums[i] + prefix[i];
        }
        dp[0][0] = 0;
        for (int i = 1; i <= n; i++) {
    
            for (int j = 1; j <= Math.min(m, i); j++) {
    
                for (int k = 0; k < i; k++) {
    
                    dp[i][j] = Math.min(dp[i][j], Math.max(dp[k][j - 1], prefix[i] - prefix[k]));
                }
            }
        }
// System.out.println(JSON.toJSONString(dp));
        return dp[n][m];
    }

Complexity analysis :

• Time complexity ：$O(M\ast N\ast N)$ , among $N$ It's an array $nums$ The length of ,$M$ Is the number of segments to split , Three layers $for$$loop$ , $k$ Maximum to $N$
• Spatial complexity ： $O(M\ast N)$$dp$ Space