题解 | #统计每个月兔子的总数#

【递归】计算month个月后一只兔子剩下的孩子的总数量（包括孩子的孩子生的）
这题和斐波那契数列的求解很像，但是我只记得递归解法，内存和速度大概超过了35%的人，考虑到递归解法慢的原因是重复计算，所以用一个静态的Map保存已经计算出的结果，最后速度提高了不过内存增多了，参考斐波那契数列的非递归解法写出来的肯定会更好。
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner scanner = new Scanner(System.in);
Integer month=null;
while(scanner.hasNext())
{
month=Integer.parseInt(scanner.nextLine());
System.out.println(1+computeTotal(month));
}

}
public static Map<Integer,Integer> monthCountMap=new HashMap<Integer, Integer>();
public static int computeTotal(int month)
{//一只刚出生的兔子出生month个月后可以生出的崽的数量
    int count=0;
    for(int i=1;i<=month;i++)
    {
        if(i>2)
        {
            if(monthCountMap.keySet().contains(month+1-i))
                count=count+1+monthCountMap.get(month+1-i);
            else
                count=count+1+computeTotal(month-i+1);
        }
    }
    monthCountMap.put(month,count);//存起来避免重复计算
    return count;
}

}