Rosalind - Mortal Fibonacci Rabbits

Aug 5, 2019 rosalind

Problem:

Please find the problem here.

Solution:

The matrix solution I used in my previous solution is still applicable, but it is cumbersome to implement. It is time to actually use dynamic programming.

Conceptually, it is easy. We know rabbits can have life from \( 0 \) to \( m - 1 \) month, so we keep an array to see how many pairs of rabbits are there at that age.

With that, every time we need to update the whole array, and most array entries are just shifted. To reduce the time spent, I maintained a variable named offset. The idea is that instead of actually moving the array entry, we can simply move the way we interpreted the array. That way, I reduced the cost from \( O(nm) \) to \( O(n + m) \).

Code: