Leetcode题解：斐波那契数

#509. 斐波那契数

斐波那契数，通常用F(n)表示，形成的序列称为斐波那契数列。该数列由0和1开始，后面的每一项数字都是前面两项数字的和。也就是：

1 2	F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

给定N，计算F(N)。

示例1：

1
2
3

输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1.

示例2：

1
2
3

输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2.

示例3：

1
2
3

输入：4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3.

提示：

0 ≤N≤ 30

package xyz.onns.leetcode;

/**
 * @Author Onns
 * @Date 2020/9/15 11:59 AM
 * @Version 1.0
 * @Website https://onns.xyz/blog/
 */
public class FibonacciNumber {
	public static void main(String[] args) {
		new FibonacciNumber().new Solution().test();
	}

	class Solution {
		public int fib(int N) {
			// base case:
			// f(0) = 0, f(1) = 1
			int pre = 0, cur = 1;
			if (N == 0) return 0;
			// all conditions:
			// i from 2 to N
			for (int i = 2; i <= N; i++) {
				// state transition:
				// f(i) = f(i-1) + f(i-2)
				int t = pre + cur;
				pre = cur;
				cur = t;
			}
			return cur;
		}

		void test() {
			System.out.println(fib(2));
			System.out.println(fib(3));
			System.out.println(fib(4));
		}
	}
}

Contents

#509. 斐波那契数