Wabbit Season

In “Rabbits and Recurrence Relations” , we mentioned the disaster caused by introducing European rabbits into Australia. By the turn of the 20th Century, the situation was so out of control that the creatures could not be killed fast enough to slow their spread (see Figure 1 ).	Figure 1. A c.1905 photo from Australia of a cart loaded to the hilt with rabbit skins.
The conclusion? Build a fence! The fence, intended to preserve the sanctity of Western Australia, was completed in 1907 after undergoing revisions to push it back as the bunnies pushed their frontier ever westward (see Figure 2). If it sounds like a crazy plan, the Australians at the time seem to have concurred, as shown by the cartoon in Figure 3. By 1950, Australian rabbits numbered 600 million, causing the government to decide to release a virus (called myxoma) into the wild, which cut down the rabbits until they acquired resistance. In a final Hollywood twist, another experimental rabbit virus escaped in 1991, and some resistance has already been observed. The bunnies will not be stopped, but they don’t live forever, and so in this problem, our aim is to expand Fibonacci’s rabbit population model to allow for mortal rabbits.	Figure 2. Western Australia’s rabbit fence is actually not the longest fence in the world as the sign claims. That honor goes to a 3,500 mile fence in southeastern Australia built to keep out dingoes. Courtesy Matt Pounsett.
	Figure 3. An 1884 cartoon from the Queensland Figaro proposing how the rabbits viewed their fence.

Problem

Recall the definition of the Fibonacci numbers from “Rabbits and Recurrence Relations”, which followed the recurrence relation Fn=Fn−1+Fn−2 and assumed that each pair of rabbits reaches maturity in one month and produces a single pair of offspring (one male, one female) each subsequent month. Our aim is to somehow modify this recurrence relation to achieve a dynamic programming solution in the case that all rabbits die out after a fixed number of months. See Figure 4 for a depiction of a rabbit tree in which rabbits live for three months (meaning that they reproduce only twice before dying).

Figure 4. A figure illustrating the propagation of Fibonacci’s rabbits if they die after three months.

Given: Positive integers n≤100 and m≤20.
Return: The total number of pairs of rabbits that will remain after the n-th month if all rabbits live for m months.

Sample Dataset

6 3

Sample Output

4

Solution：动态规划

这题首先我没想到记忆化递归的搜索方式，因为无法从最后逆推到初始状态。

状态定义：与之前斐波那契数列只有一个维度不同，因为现在需要考虑兔子最多存活m月，因此定义dp[i][j]表示第i代存活时间为j月的兔子数量。
状态转移方程：新兔子一定由已经成熟（j >= 1）的老兔子产生，而老兔子到下一代年纪也会增长一岁，同时处于m月的老兔子即将死亡。

状态初始化：从状态转移方程可得到需要单独计算第一代，即dp[1][1] = 1。
求解答案：由状态定义可知，所求第n代所有存活兔子数目，即不同年龄段的兔子总和
算法实现细节：理论分析部分序号编号从1开始，而代码中使用索引（从0开始）。

def mortalFibonacciRabbits(n: int, m: int) -> int:
    dp = [[0] * m for _ in range(n)]
    # 状态初始化
    dp[0][0] = 1  # 刚出生尚未成熟
    for i in range(1, n):
        for j in range(1, m):
            dp[i][0] += dp[i-1][j]  # 不计入 dp[i-1][0]
            dp[i][j] = dp[i-1][j-1]
    return sum(dp[n-1])
print(mortalFibonacciRabbits(*map(int, input().split())))

空间压缩：根据状态转移方程得知dp[i][...]的状态只和dp[i-1][...]的状态有关，因此dp[0...i-2][...]都可以省略。

实现细节：

1. 使用2 * m滚动数组更新：需要注意填充方向。
2. 直接用m长度数组更新：
   1. dp[i+1][j>1]的更新是直接抄左上角上一行的值，将数组行压缩后，为了避免覆盖我们需要从右往左更新。
   2. dp[i+1][0]的更新是dp[i][j>1]总和，因此从右往左更新的同时记录dp[i][j]的累加和tot，最后更新dp[i+1][0] = tot ```python def mortalFibonacciRabbits(n: int, m: int) -> int: dp = [0] * m

      状态初始化

      dp[0] = 1 # 刚出生尚未成熟 print(dp) for i in range(1, n):

      记下 sum(dp)，因为转移到 dp[i+1][0]

      tot = 0 for j in range(m - 1, 0, -1): # 从后往前更新将不会覆盖

        tot += dp[j]  # 记下之前 dp 的总和
        dp[j] = dp[j-1]  # 更新

      dp[0] = tot # 更新 dp[i+1][0] print(dp)

      更改填充方向

      return sum(dp)

print(mortalFibonacciRabbits(*map(int, input().split())))

def mortalFibonacciRabbits(n: int, m: int) -> int: dp = [[0] * m for _ in range(2)]

# 状态初始化
idx = 0
dp[idx][0] = 1  # 刚出生尚未成熟
print(dp[idx])
for i in range(1, n):
    # 先把 dp[idx^1] 这行都清空
    dp[idx^1][0] = 0
    for j in range(1, m):
        dp[idx^1][0] += dp[idx][j]  # 不计入 dp[i-1][0]
        dp[idx^1][j] = dp[idx][j-1]
    print(dp[idx^1])
    # 更改填充方向
    idx ^= 1
return sum(dp[idx])  # 注意上面更改就是最后一轮填充方向

print(mortalFibonacciRabbits(map(int, input().split()))) ‘’’ 输入：6 3 [1, 0, 0] [0, 1, 0] [1, 0, 1] [1, 1, 0] [1, 1, 1] [2, 1, 1] 4 ‘’’ ``` *复杂度分析：

• 时间复杂度：，双层循环。
• 空间复杂度：，使用空间为2 * m的滚动数组优化。