leetcode-整数拆分

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

例如，给定 n = 2，返回1（2 = 1 + 1）；给定 n = 10，返回36（10 = 3 + 3 + 4）。

注意：你可以假设 n 不小于2且不大于58。

思路

1
假设a[i]表示i对应最大乘积，已知a[0]~a[i],那么a[i+1]=（1+i；2+(i-1)...x+(i-x+1)..的最大的值）那么x+(i-x+1)的最大值如何求呢：取x*(i-x+1);a[x]*(i-x+1);x*a[i-x+1];a[x]*a[i-x+1]中的最大值；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
    public int integerBreak(int n) {
      /*
      2:1+1   1
      3:1+2   2
      4:2+2   4
      5:2+3   6
      6:3+3   9
      7:3+4 . 12
      8:2+3+3 18
      9:3+6(3+3) 27
      10:3+7(3+4) 36
      11:1+10:2+9:3+8:4+7:5+6
       */ 
        if(n ==2){
            return 1;
        }
        if(n==3){
            return 2;
        }
        int [] arr = new int[n+1];
        arr[0]=0;
        arr[1]=1;
        arr[2]=1;
        arr[3]=2;
        for(int i =4;i<n+1;i++){
            int temp =0;
            for(int j =1;j<=i/2;j++){
                int temp1 = (i-j)*j;
                int temp2 = arr[i-j]*j;
                int temp3 = (i-j)*arr[j];
                int temp4 = arr[i-j]*arr[j];
                if(temp1>temp){
                    temp =temp1;
                }
                if(temp2>temp){
                    temp =temp2;
                }
                if(temp3>temp){
                    temp=temp3;
                }
                if(temp4>temp){
                    temp=temp4;
                }
            }
            arr[i]=temp;
        }
        return arr[n];
    }
}