如何将 BigInt 用于修改后的斐波那契

Question

我正在尝试解决这个问题： problem

并且通过动态规划我能够解决问题，这里是目前的代码：

    import java.util.Scanner;
    public class Dy
    {
        static long[] storage = new long[20];
        public static void main(String[] args)
        {
            Scanner sx = new Scanner(System.in);

            storage[0] = sx.nextInt();
            storage[1] = sx.nextInt();
            int x = sx.nextInt();

            System.out.println(beast(x-1));


        }

    public static long beast(int n)
    {
        if(n==0)
            return storage[n];
        if(n==1)
            return storage[n];

        if(storage[n]!=0)
            return storage[n];

        storage[n] = (beast(n-1)*beast(n-1)) + beast(n-2);

        return storage[n];
    }
}

但真正的麻烦是，如果n是20左右，即使long数据类型也不会保存值，所以选择显然是BigInteger ，但作为一名学习者，我想知道如何将 BigInteger 与 Java 中的数组一起使用？任何帮助将不胜感激，谢谢！

Answer 1

您可以使用 Map<Integer, BigInteger> 之类的东西，

static Map<Integer, BigInteger> storage = new HashMap<>();

public static void main(String[] args) {
    Scanner sx = new Scanner(System.in);

    // Add 0 and 1.
    storage.put(0, BigInteger.valueOf(sx.nextInt()));
    storage.put(1, BigInteger.valueOf(sx.nextInt()));
    int x = sx.nextInt();

    System.out.println(beast(x - 1));
}

public static BigInteger beast(int n) {
    if (!storage.containsKey(n)) {
        BigInteger t = beast(n - 1);
        storage.put(n, t.multiply(t).add(beast(n - 2)));
    }
    return storage.get(n);
}

如何将 BigInt 用于修改后的斐波那契

how to use BigInt for a modified Fibonacci

java

biginteger

dynamic-programming