O(n)=O(n-2)+2^(n-3)，大数高精度
import java.util.*; import java.math.*; public class Main { static BigInteger a[]=new BigInteger[1010]; static BigInteger b[]=new BigInteger[1010]; public static void init() { BigInteger bb=BigInteger.valueOf(2); b[0]=BigInteger.valueOf(1); for(int i=1;i<=1000;i++) b[i]=b[i-1].multiply(bb); a[1]=BigInteger.valueOf(0); a[2]=BigInteger.valueOf(1); a[3]=BigInteger.valueOf(1); for(int i=4;i<=1000;i++) { a[i]=a[i-2].add(b[i-3]); } } public static void main(String[] args) { init(); Scanner sc=new Scanner(System.in); while(sc.hasNext()) { int nn=sc.nextInt(); System.out.println(a[nn]); } } }
转载于:https://www.cnblogs.com/Wangwanxiang/p/8440787.html
相关资源：数据结构—成绩单生成器