所屬專題:[組合數學](README.md);[動態規劃](README.md)
 
## 問題
回顧一下在[“兔子與遞推關系”](FIB.md)問題中關于“斐波那契數”的定義,它滿足遞推式`$ F_n=F_{n-1}+F_{n-2} $`,假定每一對兔子在出生一個月后成熟,并從那時開始每個月繁殖新的一對兔子(一雄一雌)。
我們的目標是以某種方式改進這個遞推關系,實現一個動態規劃解決方案,以描述兔子將在固定的若干個月后去世的情況。下圖描述了每只兔子存活三個月時的家族樹(這意味著它們在去世前只繁殖兩次)。(圖片來源:[ROSALIND](http://rosalind.info/media/problems/hamm/))
*****
<div align="center"><img src="http://rosalind.info/media/problems/fibd/mortal_rabbit_tree.png"></div>
<div align="center">斐波那契兔子的繁殖示意圖,假設兔子壽命為三個月。</div>
*****
**輸入:** 兩個正整數,`$ n \le 100 $`與`$ m \le 20 $`.
**輸出:** `$ n $`個月后總共存活的兔子對數,假設所有兔子壽命均為`$ m $`個月。
**樣例數據:**
~~~
6 3
~~~
**樣例輸出:**
~~~
4
~~~
 
## 背景知識
該問題在傳統的“斐波那契兔子”問題上加入了兔子壽命的限定,主要解決思路仍是動態規劃,設定好狀態轉移方程(加上兔子死亡數一項)。詳情請查閱ROSALIND網站上[關于該問題的背景說明](http://rosalind.info/problems/fibd/)。
 
## 解答
```
def mortal_fib(n, m):
"""給定兔子壽命為m個月,計算n個月后兔子種群的對數"""
if m==1:
if n==1:
result = 1
else:
result = 0
elif m==2:
result = 1
else:
rabbits = [0, 1, 1]
for i in range(3, m+1):
rabbits.append(rabbits[-1]+rabbits[-2])
if n<=m:
result = rabbits[n]
else:
rabbits.append(rabbits[-1]+rabbits[-2]-1)
for i in range(m+2, n+1):
rabbits.append(rabbits[-1]+rabbits[-2]-rabbits[-(m+1)])
result = rabbits[n]
return result
## --main--
with open("rosalind_fibd.txt", 'r') as f1:
n,m = map(int, f1.read().split())
result = mortal_fib(n, m)
with open("rosalind_fibd_out.txt", 'w') as f2:
f2.write(str(result))
```