问题描述:

I am trying to solve this: problem

And by Dynamic programming I am able to solve the problem, here is the code so far:

 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];

}

}

But the real trouble here is , if n is say around 20, even long data type won't hold the value, so the choice is obviously BigInteger , but as a learner, I was wondering how to use BigInteger with Arrays in Java? Any help will be much appreciated, thanks!

网友答案:

You could use a Map<Integer, BigInteger> and something like,

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);
}
相关阅读:
Top