所属专题：[组合数学](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))
```
