package y2019.Algorithm.array;

/**
 * @ProjectName: cutter-point
 * @Package: y2019.Algorithm.array
 * @ClassName: Fib
 * @Author: xiaof
 * @Description: 509. Fibonacci Number
 * The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence,
 * such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
 *
 * F(0) = 0,   F(1) = 1
 * F(N) = F(N - 1) + F(N - 2), for N > 1.
 *
 * Input: 2
 * Output: 1
 * Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.
 *
 * @Date: 2019/7/4 9:01
 * @Version: 1.0
 */
public class Fib {

    public int solution(int N) {

        //因为N每次只需要获取上一个，和上上个的数据，dp一维数组
        int pre1 = 0;
        int pre2 = 1;
        if(N == 0) {
            return 0;
        } else if (N == 1) {
            return pre2;
        } else if (N == 2) {
            return pre2;
        }

        pre1 = pre2 = 1;
        for(int i = 3; i <= N; ++i) {
            int temp = pre2;
            pre2 += pre1;
            pre1 = temp;
        }

        return pre2;
    }

}