509. 斐波那契数

509. 斐波那契数

递归解法：

时间复杂度：O(2^n)
空间复杂度：O(n)

    class Solution {
        public int fib(int n) {
            if (n == 0) {
                return 0;
            }
            if(n == 1){
                return 1;
            }
            return fib(n - 1) + fib(n - 2);
        }
    }

动态规划解法：

时间复杂度：O(n)
空间复杂度：O(1)

    class Solution {
        public int fib(int n) {
            if (n < 2) {
                return n;
            }

            // - 动态规划实现
            // - 前一个节点
            int previousNode = 0;
            // - 当前节点
            int currentNode = 0;
            // - 最终结果
            int result = 1;

            for (int i = 2; i <= n; i++) {
                previousNode = currentNode;
                currentNode = result;
                result = previousNode + currentNode;
            }

            return result;
        }
    }