题解 | #斐波那契数列#

• 这道题是非常简单的动态规划题，我记得我大一刚入学，学校教的就是这个，现在也算是回顾一下吧。
• 将一个问题划分为若干个子问题，比如f(5)=f(4)+f(3)=（f(3)+f(2)）+（f(2)+f(1)）=3f(2)+2f(1)
• 从上面，可以观察到f(4)=f(3)+f(2),f(3)=f(2)+f(1)，由此可以采用递归的方式，将每个大问题最终 分解为是f(1)还是f(2)的问题上，以此解决问题。
• 如果还不明白，你可以试着画一张树状图，可能更好理解
• 当输入数字或者数字为1或2时，函数返回值为1
• 当大于2时，直接返回f(n-1)+f(n-2)

class Solution {
public:
    int Fibonacci(int n) {
        if(n==1||n==2)return 1;
        else if(n>2)return Fibonacci(n-1)+Fibonacci(n-2);
        return 0;
    }
};