[leetcode] dynamic programming solution partition array ii[arctic fox]

Their thinking ：

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 ~

{:width=“350px”}{:align=“left”}

Define the State

$dp[i]$： An array of former $i$ The number is $nums[0,1...i-1]$, It's cut $Y-1$ The knife , Divided into $Y$ An array , The maximum number of arrays shall not exceed $K$, The value of each array becomes the maximum value , The maximum sum after segmentation , Pictured above , When divided into $Y=3$ When there are two parts , The maximum value of the first part is $15$, The second part is $9$, The third part $10$, Each value of each part rises to a local value of the current part $max$, The red font is the new value , After accumulation , Find the maximum

Transfer equation

{:width=“450px”}{:align=“left”}

Want to ask $dp[i]$, This is a An array of former $i$ The number is $nums[0,1...i-1]$, It's cut $Y-1$ The knife , Divided into $Y$ An array , The maximum number of arrays shall not exceed $K$, The value of each array becomes the maximum value , The maximum sum after segmentation

• seek $dp[i-1]$, Represents the front of an array $i$ The number is $nums[0,1...i-2]$, The second part is $nums[i-1]$, in other words $dp[i-1]$ + $max(nums[i-1])$*$(i-(i-1))$
• seek $dp[i-2]$, Represents the front of an array $i-1$ The number is $nums[0,1...i-3]$, The second part is $nums[i-2...i-1]$, in other words $dp[i-2]$ + $max(nums[i-2...i-1])$ * $(i-(i-2))$
• seek $dp[i-3]$, Represents the front of an array $i-2$ The number is $nums[0,1...i-4]$, The second part is $nums[i-3...i-1]$, in other words $dp[i-3]$ + $max(nums[i-3...i-1])$ * $(i-(i-3))$
• …
• seek $dp[0]$, Represents the front of an array $1$ The number is $nums[0,0]$, The second part is $nums[0...i-1]$, in other words $dp[0]$ + $max(nums[0...i-1])$ * $(i-(0))$

Find the maximum of the above

Can be derived $dp[i]$=$max$($dp[i]$,$dp[j]+(i-j)\ast MAX$), among $MAX$ yes $nums[j...i-1]$ Local maximum in the range , Once the maximum value is found , All values in this range are changed to this local maximum $MAX$, among 0=<$j$<$i$

Initialize boundary

$i-j$ If it is greater than $K$, Back $nums[i...n]$ There will be no way to cover this part , A condition :$i-j$<=$K$

$j$>=0, There's nothing to say about this

$dp$ During initialization, the capacity is $n+1$, Required $dp[n]$ Express An array of former $n$ The number is $nums[0,1...n]$, It's cut $Y-1$ The knife , Divided into $Y$ An array , The maximum number of arrays shall not exceed $K$, The value of each array becomes the maximum value , The maximum sum after segmentation

Coding techniques

• $i$ Traverse from left to right ,$j$ Starts $i-1$ Traverse from right to left
• Note the local maximum $MAX$

Complete code

    public int maxSumAfterPartitioning(int[] A, int K) {
        int n = A.length;
        int[] dp = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            int j = i - 1;
            int max = dp[i];
            while ((i - j) <= K && j >= 0) {
                max = Math.max(max, A[j]);
                dp[i] = Math.max(dp[i], dp[j] + (i - j) * max);
                j--;
            }
        }
        return dp[n];
    }

class Solution {
public:
    int maxSumAfterPartitioning(vector<int>& A, int K) {
        // f[i] = max(f[j] + (i-j)*max(A[j..i]))

        int n = A.size();
        vector<int> f(n+1);
        for (int i = 0; i <= n; i++) {
            int curMax = 0;
            // consider past integers [j...i]
            for (int j = i-1; (i-j)<=K && j>=0; j--) {
                curMax = max(curMax, A[j]);
                f[i] = max(f[i], f[j] + (i-j)*curMax);
            }
        }
        return f[n];
    }
};

summary

• The topic of dynamic planning , We need to think of some basic situations , Think like mathematical induction