一个今日头条面试题的解析答题思路，赶紧get

头条笔试题：

母牛从3-7岁初每年会生产1头小母牛，10岁后死亡（10岁仍然存活），假设初始有1头刚出生的母牛，请问第n年有多少头母牛？（年从第一年开始计数）

小编是一个有着6年工作经验的工程师，关于C++，编程，自己有做材料的整合，一个完整的C++编程学习路线，学习资料和工具，能够进我的群7253，-91790收取，免费送给大家，希望你也能凭着自己的努力，成为下一个优秀的程序员

解题思路：

在没有任何思路的情况下，可以先暴力分析，顺着题意将给出的示例推导出来，然后再从中观察规律，找到更为便捷的方法；

1. 先暴力分析：从第一年开始，计算每年的母牛个数；

基本思路：以最开始的母牛为基准进行分析，分析每年它生产的孩子的个数，最后加1 就是每年牛的个数；

观察上述分析结果，我们会发现：有很多重复地方，即母牛这题含有重复子结构，最常用的方法就是：用数组变量，将重复的地方记录下来。

（1）sum：记录每次的求和部分

（2）opt[ i ]：记录第 i 年母牛的个数， opt[ -1] ：表示最终的输出结果

（3）一次循环遍历，记录 sum 和 opt[ i ]，时间复杂度：O(n)

Python代码：

# 母牛生产import sysfor line in sys.stdin:n=int(line)ifn<3:print('1') else:opt = [0for i in range(n+1)] opt[0] = -1opt[1] =1opt[2] =1sum=0for i in range(3,n+1):ifi >=3andi <=7:sum=sum+ opt[i -2] opt[i] =sum+1elif i >=8andi <=10:sum=sum- opt[i-7] + opt[i-2] opt[i] =sum+1else:sum=sum- opt[i-7] + opt[i-2] opt[i] =sumprint(opt[-1])