所屬專題：[組合數學](README.md)；[動態規劃](README.md)
 
## 問題
在著名的“斐波那契兔子”問題中，有如下的假定：
1. 兔子種群在第一個月從一對新生的兔子開始；
2. 兔子們在出生一個月后達到生育年齡；
3. 在任何一個月，每一只育齡兔子會與另一只育齡兔子交配；
4. 兔子交配后一個月，會生下一對兔子（一只雄兔與一只雌兔）；
5. 不考慮兔子壽命限制，兔子會一直繁殖下去。
在這里，我們對“斐波那契兔子”問題進行推廣，每對兔子交配后一個月，將產下`$ k $`對兔子，求解若干個月后的兔子總對數。
**輸入：** 兩個正整數`$ n\le40 $`與`$ k\le5 $`。
**輸出：** 第`$ n $`個月時兔子的總對數。假定我們從1對兔子開始，在每一代，一對兔子會生下`$ k $`對兔子（而不是原始“斐波那契兔子”問題中的1對）。
**樣例數據：**
```
5 3
```
**樣例輸出：**
```
19
```
 
## 背景知識
這個問題來源于歷史上著名的數學問題“斐波那契兔子”問題。在原問題的設定中，兔子數量隨時間（代際）發展的變化如下圖所示：（圖片來源：[ROSALIND](http://rosalind.info/media/problems/fib/)）
*****
<div align="center"><img src="http://rosalind.info/media/problems/fib/rabbit_tree.thumb.png"></div>
<div align="center">斐波那契兔子數量在前六個月的增長圖示</div>
*****
斐波那契兔子問題還涉及遞推數列等數學問題。詳情請查閱ROSALIND網站上[關于該問題的背景說明](http://rosalind.info/problems/fib/)。
 
## 解答
```
def fib_new(n, k):
"""給定兔子代數n與單次繁殖數k，遵循斐波那契規則，計算n代兔子的總數"""
num = [0, 1, 1]
for i in range(3, n+1):
num.append(k*num[i-2]+num[i-1])
return num[n]
## --main--
with open("rosalind_fib.txt", 'r') as f1:
n,k = map(int, f1.read().split())
with open("rosalind_fib_out.txt", 'w') as f2:
f2.write(str(fib_new(n, k)))
```
