Li Kou 343 integer partition dynamic programming

Title Description

Given a positive integer  n , Divide it into  k  individual   Positive integer   And （ k >= 2 ）, And maximize the product of these integers .

return   The maximum product you can get  .

Their thinking

The six steps of using dynamic programming to solve problems ：

• determine dp Array and the meaning of array subscript （dp The array may be one-dimensional or two-dimensional ）;
  • According to the title , Will define arr [ i ] Is a positive integer i After splitting into the sum of at least two positive integers , The maximum product of these positive integers ;
• Determine the recurrence formula （ State transition equation ）;
  • Suppose we start with a positive integer  i (i>2)  Take out a positive integer  j (1<= j < i), Is equivalent to  i  Split into  j  and  i-j  Two parts , Then there are two options （ state ）：

    • i-j Part no longer split , Then at this time, integer i The split product is j * (i-j)

    • i-j Part no longer split , Then at this time, integer i The split product is j * arr(i-j)

  • therefore , It can be concluded that the recurrence formula is arr[i] = max{max(j*(i-j), j*arr(i-j))}, among 1<= j < i, That's traversal j, Calculate in each cycle max(j*(i-j), j*arr(i-j)), After the final traversal , take max(j*(i-j), j*arr(i-j)) The maximum value of is taken as arr[i] The value of .

• initialization dp Array ;
  • ​​​​​​​​​​​​​​ Array initialization ： Subject requirements n>=2, therefore , about 0 and 1 We assign it as 0 that will do ;
• determine dp The traversal order of the array , May be forward traversal 、 Reverse traversal 、 Obliquely ergodic ;
• Give an example to deduce dp Array , Ensure the accuracy of derivation ;

I / O example

 

Code

class Solution {
    public int integerBreak(int n) {
        if(n == 1)return 0;
        int[] arr = new int[n + 1];
        arr[0] = arr[1] = 0;
        for(int i = 2; i <= n; i++){
            int maxmultip = 0;
            for(int j = 1; j < i; j++){
                maxmultip = Math.max(maxmultip,Math.max(j*(i - j),j*(arr[i - j])));
            } 
            arr[i] = maxmultip;          
        }
        return arr[n];
    }
}