所屬專題：[組合數學](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))
```
