f(n) = f(n-1)+2*f(n-2) 使用记忆化搜索+BigInteger 水过

import java.io.*;
import java.util.*;
import java.math.*;

public class Main {
    //遞推公式：f(n) = f(n-1)+2*f(n-2)
    //使用記憶化搜索
    
    public static BigInteger[] data = new BigInteger[251];
    public static BigInteger f(int n)
    {
        if(n==0) return BigInteger.valueOf(1);
        if(n==1) return BigInteger.valueOf(1);
        if(n==2) return BigInteger.valueOf(3);
        if(data[n].compareTo(BigInteger.valueOf(-1))!=0)
            return data[n];

        data[n] =  f(n-1).add(f(n-2).multiply(BigInteger.valueOf(2)));
        return data[n];
    }

    public static void main(String[] args) {
       int n;
       Scanner in = new Scanner(System.in);
       while(in.hasNextInt()){
           for(int i=0;i<251;i++){
               data[i] = BigInteger.valueOf(-1);
           }
           n = in.nextInt();
           System.out.println(f(n));
       }
    }

}