FilesExpand file tree

master

/

test04.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

52 lines (49 loc) · 1.09 KB

master

/

test04.java

Copy path

Top

File metadata and controls

• Code
• Blame

52 lines (49 loc) · 1.09 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

51

52

package byteDance;

/**

* Created by lizeyang on 2020/5/12.

* 剪绳子

*/

public class test04 {

//不会溢出的情况,时间复杂度O(n*n/2)

public static int test(int n){

if(n==1){

return 1;

}else if(n==2){

return 2;

}else if(n==3){

return 3;

}

int[] dp = new int[n+1];

dp[0] = 0;

dp[1] = 1;

dp[2] = 2;

dp[3] = 3;

for(int i=4;i<=n;i++){

for(int j = 1;j<=i/2;j++){

dp[i] = Math.max(dp[j]*dp[i-j],dp[i]);

}

}

return dp[n];

}

//考虑溢出的情况,时间复杂度O(1)

public static int test1(int n){

if(n==1){

return 1;

}else if(n==2){

return 2;

}else if(n==2){

return 3;

}

int res = 1;

while(n>4){

res *= 3;

n -= 3;

}

return res*n;

}

public static void main(String[] args) {

int n = 10;

System.out.println(test(n));

System.out.println(test1(n));

}

}