本文共 1204 字，大约阅读时间需要 4 分钟。

爱奇艺 2019校招 Android方向试卷在线考试

编程题|20.0分2/2

清雨的自助餐

时间限制：C/C++语言 1000MS；其他语言 3000MS

题目描述：

清雨又在吃自助餐了。

排在清雨面前的有N种食物，排成一排，清雨可以选择其中的若干种食物，但是不能连续选择相邻的食物。因为清雨很挑食，当所有食物都不合口味时，他可以一种都不选，即一个都不选也算为一种方法。

请问他有多少种选择食物的方法呢？

输入

一个整数n（1 <= n <= 90）

输出

一个正整数表示答案

样例输入

3

样例输出

5

Hint

样例解释：有3种食物，方案为1、2、3、13、不选，共5种

思路：

刚开始以为深搜，然后发现到了最大90的时候运行出不来，超时。

结果一一列举发现，1个数字，选择或者不选，a[1]=2种情况

2个数字，1， 2， 不选，a[2]=3种情况

3个数字, 1， 2， 3， 13， 不选，a[3]=5种情况

4个数字，1， 2， 3， 4， 13， 14， 24， 不选，a[4]=8种情况

=========这不就是前两项和累加吗？斐波那契额啊

AC代码：

import java.util.Scanner;public class Main {    public static void main(String[] args) {        Scanner cin = new Scanner(System.in);        int n = cin.nextInt();        cin.close();        System.out.println(fibonacci(n));    }    private static long fibonacci(int n) {        long y1 = 2, y2 = 3, y3 = 5, y = 0;        for (int i = 4; i <= n; ++i) {            y = y3 + y2;            y2 = y3;            y3 = y;        }        if (n == 1)            return y1;        if (n == 2)            return y2;        if (n == 3)            return y3;        return y;    }}

记住一定要返回为long，数据很大，用int只能通过21%

=======================Talk is cheap, show me the code==========================

转载地址：https://liuchenyang0515.blog.csdn.net/article/details/82889679 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！