Hat's Fibonacci

题目链接
Problem Description
A Fibonacci sequence is calculated by adding the previous two members the sequence, with the first two members being both 1.
F(1) = 1, F(2) = 1, F(3) = 1,F(4) = 1, F(n>4) = F(n - 1) + F(n-2) + F(n-3) + F(n-4)
Your task is to take a number as input, and print that Fibonacci number.

Input
Each line will contain an integers. Process to end of file.

Output
For each case, output the result in a line.

Sample Input
100

Sample Output
4203968145672990846840663646

Note:
No generated Fibonacci number in excess of 2005 digits will be in the test data, ie. F(20) = 66526 has 5 digits.

解题思路:Java大数模板

import java.math.BigInteger;
import java.util.Scanner;public class Main {
    public static void main(String[] args) {
    // TODO Auto-generated method stubScanner in = new Scanner(System.in);BigInteger arr[] = new BigInteger[1000001];//数组开到大约三百万即可,再大不行while(in.hasNextInt()){
    int a = in.nextInt();arr[1] = arr[2] = arr[3] = arr[4] = BigInteger.ONE;for(int i = 5;i <= a;i++)arr[i] = arr[i - 1].add(arr[i - 2]).add(arr[i - 3]).add(arr[i - 4]);System.out.println(arr[a]);}}
}