动态规划

package com.banmoon.arithmetic;
​
public class Fibonacci {
​
    public static long fibonacci(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }
​
}

package com.banmoon.arithmetic;
​
import java.util.HashMap;
import java.util.Map;
​
public class Fibonacci {
​
    private static Map<Integer, Long> map = new HashMap<>();
​
    public static long fibonacci(int n) {
        if (n == 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else if (map.containsKey(n)) {
            return map.get(n);
        } else {
            long result = fibonacci(n - 1) + fibonacci(n - 2);
            map.put(n, result);
            return result;
        }
    }
​
}

package com.banmoon.arithmetic;
​
public class Fibonacci {
​
    public static long fibonacci(int n) {
        // 创建一个数组来存储子问题的解，初始值为0
        long[] dp = new long[n + 1];
        // 初始化前两个数的值
        dp[0] = 0;
        dp[1] = 1;
        // 从第三个数开始迭代计算
        for (int i = 2; i <= n; i++) {
            // 通过状态转移方程计算当前数的值
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        // 返回第n个数的值
        return dp[n];
    }
​
}