java - 斐波那契数列为负数

Question

我使用动态编程技术编写了以下代码，但是当我对数字 220 运行斐波那契时，我得到一个负数。这个程序有错误吗？

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Fibonaci {

    public static void main(String[] args) {
        System.out.println(" number ");
        long startTime = System.currentTimeMillis();
        HashMap<Integer, Integer> memoized = new HashMap<Integer, Integer>();
        int fib = fibonanci(220, memoized);
        System.out.println(" Total Time "
                + (System.currentTimeMillis() - startTime));

    }

    private static int fibonanci(int n, HashMap<Integer, Integer> memoized) {
        System.out.println(" n " + n);
        if (memoized.containsKey(n)) {
            return memoized.get(n);
        }

        if (n <= 0) {
            return 0;
        }
        if (n <= 2) {
            return 1;
        } else {
            int febonani = fibonanci(n - 1, memoized)
                    + fibonanci(n - 2, memoized);
            System.out.println(" febonani " + febonani);
            if (!memoized.containsKey(n)) {
                memoized.put(n, febonani);
            }
            return febonani;
        }
    }


}

Answer 1

斐波那契数增长非常快，java中的整数只适合从-2^31到2^31 - 1的值。第 220 个斐波那契数是 4244200115309993198876969489421897548446236915(大约 2^151)，这远远超出了这个范围，因此你得到 integer overflow 。