动态规划：斐波那契数 - 动态规划 - 数据结构与算法 | Aayu Yain = 学无止境 = 世界上大部分事，都没太大意义。真理与热爱除外

# 题目描述

# 思路与题解

第一想到的应该就是递归，用递归尝试后爆溢栈了，于是便想到用一个数组记录下来已算出的斐波那契数。我犯的一个低级错误就是把 if (n == 1 || n == 0) return n; 刚开始没有放到 fib 函数里，导致系统输入 0 时，直接 n - 1 = -1，数组越界报错了 🤣 长时间不思考果然脑袋就变笨了

看了官方题解后又有了收获，用滚动数组的思想，就可以将递归函数转换为 for 循环，用自下而上的方法去求解子问题，秒的很

	class Solution {
	public:
	int data[31];
	bool flag[31];

	void init() {
	for (int i = 0; i < 31; i++) {
	data[i] = 0;
	flag[i] = false;
	}
	data[1] = 1;
	data[0] = 0;
	flag[1] = flag[0] = true;
	}

	int fib(int n) {
	init();
	if (n == 1 \|\| n == 0) return n;
	return recur(n-1) + recur(n-2);
	}

	int recur(int n) {
	if (flag[n]) return data[n];
	data[n] = recur(n-1) + recur(n-2);
	flag[n] = true;
	return data[n];
	}
	};

	class Solution {
	public:
	int fib(int n) {
	if (n < 2) return n;
	int p, q, r;
	p = q = 0;
	r = 1;
	for (int i = 2; i <= n; i++) {
	p = q;
	q = r;
	r = p + q;
	}
	return r;
	}
	};