FilesExpand file tree

 master

/

GuessNumberHigherOrLowerII375.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

99 lines (88 loc) · 3.04 KB

 master

/

GuessNumberHigherOrLowerII375.java

Copy path

Top

File metadata and controls

• Code
• Blame

99 lines (88 loc) · 3.04 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

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

/**

* We are playing the Guess Game. The game is as follows:

*

* I pick a number from 1 to n. You have to guess which number I picked.

*

* Every time you guess wrong, I'll tell you whether the number I picked is

* higher or lower.

*

* However, when you guess a particular number x, and you guess wrong, you

* pay $x. You win the game when you guess the number I picked.

*

* Example:

* n = 10, I pick 8.

* First round: You guess 5, I tell you that it's higher. You pay $5.

* Second round: You guess 7, I tell you that it's higher. You pay $7.

* Third round: You guess 9, I tell you that it's lower. You pay $9.

*

* Game over. 8 is the number I picked.

* You end up paying $5 + $7 + $9 = $21.

*

* Given a particular n ≥ 1, find out how much money you need to have to

* guarantee a win.

*/

public class GuessNumberHigherOrLowerII375 {

// // LTE

// public int getMoneyAmount(int n) {

// return getMoneyAmount(1, n);

// }

// public int getMoneyAmount(int l, int r) {

// if (l >= r) return 0;

// if (l + 1 == r) return l;

// if (l + 2 == r) return l + 1;

// int res = Integer.MAX_VALUE;

// for (int i=l; i<=r; i++) {

// int left = getMoneyAmount(l, i-1);

// int right = getMoneyAmount(i+1, r);

// res = Math.min(res, Math.max(left, right) + i);

// }

// return res;

// }

public int getMoneyAmount(int n) {

return getMoneyAmount(1, n, new int[n][n]);

}

public int getMoneyAmount(int l, int r, int[][] memo) {

if (l >= r) return 0;

if (memo[l-1][r-1] != 0) return memo[l-1][r-1];

int res = Integer.MAX_VALUE;

for (int i=l; i<=r; i++) {

int left = getMoneyAmount(l, i-1, memo);

int right = getMoneyAmount(i+1, r, memo);

res = Math.min(res, Math.max(left, right) + i);

}

memo[l-1][r-1] = res;

return res;

}

public int getMoneyAmount2(int n) {

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

for (int l=1; l<=n; l++) {

for (int i=1; i<=n-l; i++) {

int j = i+l;

int tmp = Integer.MAX_VALUE;

for (int k=i; k<=j; k++) {

int left = i <= k-1 ? dp[i][k-1] : 0;

int right = k+1 <= j ? dp[k+1][j] : 0;

tmp = Math.min(tmp, Math.max(left, right) + k);

}

dp[i][j] = tmp;

}

}

return dp[1][n];

}

public int getMoneyAmount3(int n) {

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

for (int l=1; l<=n; l++) {

for (int i=1; i<=n-l; i++) {

int j = i+l;

int tmp = Integer.MAX_VALUE;

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

int left = i <= k-1 ? dp[i][k-1] : 0;

int right = k+1 <= j ? dp[k+1][j] : 0;

tmp = Math.min(tmp, Math.max(left, right) + k);

}

dp[i][j] = tmp;

}

}

return dp[1][n];

}

}