牛客题解-NC65斐波那契数列

发表于 更新于 分类于 阅读次数：

题目

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。

n≤39

示例1：

输入：

1
4

输出：

1
3

思路

分析

该问题为经典的动态规划问题。

对于动态规划问题，关键就是找到初始状态和状态转换方程。

本体的初始状态为

f（0）= 0

f（1）= 1

状态转换方程为

f（n） = f（n-1）+ f（n-2）

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public int Fibonacci(int n) {
        if(n < 2) return n;
        int a = 0, b = 1;
        int sum = 0;
        for(int i = 0; i < n; i++){
            sum = a + b;
            a = b;
            b = sum;
        }
        return a;
    }
}