FilesExpand file tree

master

/

Fib.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

103 lines (96 loc) · 1.45 KB

master

/

Fib.java

Copy path

Top

File metadata and controls

• Code
• Blame

103 lines (96 loc) · 1.45 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

100

101

102

103

package com.algs;

public class Fib

{

/**

* Recursive

*/

public static int fib(int n)

{

if (0 == n)

{

return 0;

}

else if (1 == n)

{

return 1;

}

else

{

return fib(n - 1) + fib(n - 2);

}

}

/**

* tail recursive

*

* @param args

*/

public static int fib2(int n)

{

return fib2Helper(1, 0, n);

}

private static int fib2Helper(int a, int b, int n)

{

if (n == 0)

{

return b;

}

return fib2Helper(a + b, a, n - 1);

}

/**

* while

*

* @param args

*/

public static int fib3(int n)

{

if (0 == n)

{

return 0;

}

else if (1 == n)

{

return 1;

}

int a = 1, b = 0;

while (n-- > 0)

{

int temp = a;

a = a + b;

b = temp;

}

return b;

}

/**

* 自底向上包含"动态规划"思想的解法

*

* @param n

* @return 第n个斐波那契数

*/

public static long downToTopReslove(int n)

{

if (n == 0)

{

return 0;

}

else if (n == 1)

{

return 1;

}

else

{

long[] fibonacciArray = new long[n + 1]; // fibonacciArray[i]表示第i个斐波那契数

fibonacciArray[0] = 0;

fibonacciArray[1] = 1;

for (int i = 2; i <= n; i++)

{

// 注意由于fibonacciArray[0]表示第0个元素，这里是i <= n，而不是i < n

fibonacciArray[i] = fibonacciArray[i - 1] + fibonacciArray[i - 2];

}

return fibonacciArray[fibonacciArray.length - 1];

}

}

public static void main(String[] args)

{

System.out.println(downToTopReslove(100));

}

}