一個今日頭條筆試題的答題思路

（點選上方快速關註並設定為星標，一起學Python）

來源：JeannieLi    連結：

http://www.cnblogs.com/xdliyin/p/10778583.html

頭條筆試題：

母牛從3-7歲初每年會生產1頭小母牛，10歲後死亡（10歲仍然存活），假設初始有1頭剛出生的母牛，請問第n年有多少頭母牛？（年從第一年開始計數）

解題思路：

在沒有任何思路的情況下，可以先暴力分析，順著題意將給出的示例推匯出來，然後再從中觀察規律，找到更為便捷的方法；

1. 先暴力分析：從第一年開始，計算每年的母牛個數；

基本思路：以最開始的母牛為基準進行分析，分析每年它生產的孩子的個數，最後加1 就是每年牛的個數；

觀察上述分析結果，我們會發現：有很多重覆地方，即母牛這題含有重覆子結構，最常用的方法就是：用陣列變數，將重覆的地方記錄下來。

（1）sum：記錄每次的求和部分

（2）opt[ i ]：記錄第 i 年母牛的個數， opt[ -1] ：表示最終的輸出結果

（3）一次迴圈遍歷，記錄 sum 和 opt[ i ]，時間複雜度：O(n)

Python程式碼：

# 母牛生產
import sys
for line in sys.stdin:
    n = int(line)
    if n < 3:
        print('1')
    else:
        opt = [0 for i in range(n + 1)]
        opt[0] = -1
        opt[1] = 1
        opt[2] = 1

        sum = 0
        for i in range(3, n+1):
            if i >=  3 and i <=7:
                sum = sum + opt[i - 2]
                opt[i] = sum + 1

            elif i >= 8 and i <= 10:
                sum = sum - opt[i-7] + opt[i-2]
                opt[i] = sum + 1

            else:
                sum = sum - opt[i-7] + opt[i-2]
                opt[i] = sum

        print(opt[-1])