Leetcode skimming: dynamic programming 06 (integer splitting)

343. integer partition

Force button topic link

Given a positive integer n, Split it into at least two positive integers and , And maximize the product of these integers . Return the maximum product you can get .

Example 1:

• Input : 2
• Output : 1
• explain : 2 = 1 + 1, 1 × 1 = 1.

Example 2:

• Input : 10
• Output : 36
• explain : 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
• explain : You can assume n Not less than 2 And not more than 58.
  

If I know the result .

class Solution {
    
    public int integerBreak(int n) {
    
        int[] arr = new int[]{
    1, 2, 4, 6, 9, 12, 18, 27, 36, 54, 81, 108, 162, 243, 324, 486, 729, 972, 1458
                , 2187, 2916, 4374, 6561, 8748, 13122, 19683, 26244, 39366, 59049, 78732, 118098, 177147
                , 236196, 354294, 531441, 708588, 1062882, 1594323, 2125764, 3188646, 4782969, 6377292, 9565938
                , 14348907, 19131876, 28697814, 43046721, 57395628, 86093442, 129140163, 172186884, 258280326, 387420489, 516560652, 774840978, 1162261467, 1549681956};
        return arr[n - 2];
    }
}

Dynamic programming

    public static int integerBreak(int n) {
    
        int[] dp = new int[n + 1];
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
    
            for (int j = 1; j * 2 <= i; j++) {
    
                // More than half of the re segmentation is still repeated 
                // dp[i] Record the current maximum 
                // dp[i-j]*j dp[i-j] It can be regarded as the maximum product after segmentation 
                // (i-j)*j  The product of two numbers 
                dp[i] = Math.max(dp[i], Math.max(dp[i - j] * j, (i - j) * j));
            }
        }
        return dp[n];
    }

Greedy Algorithm , This is mathematically proven .