I will explain here a solution to this problem.
It requires less than 20 lines of code, or even shorter. The key point is understanding the problem itself.
Understanding the Problem
I am redrawing here the example case illustrated in the problem. Let’s keep track of every individual. Since they are mentioned as pair, let's name them accordingly, although considering them individual rabbit/person wouldn’t make a difference.
So, the journey starts with Adam/Eve. They are children (0 months of age) in the 1st month, so unable to breed yet.
In 2nd month, they have become adults and capable to breed now.
In the 3rd month, we get 1st breed from Adam/Eve — Kenan/Jen. Also, Adam/Eve get older. Since Kenan/Jen are children, they are not capable to breed yet.
In the 4th month, Adam/Eve give birth to their 2nd breed, Abel/Amy, but remember, everyone lives maximum 3 months, so Adam/Eve are not alive in the 4th month. In parallel, Kenan/Jen give birth to their 1st breed and they get older.
And so on …
The Solution
Also, as you know, in dynamic programming, we usually maintain a table and gradually keep building it. An obvious choice is defining a table where, row represents months, and column represents number of population at an age.
So, for a given input n (months) and m (lifespan), we create a m X m table, initializing all values with 0.
Then we set [1][0] = 1, since in 1st month, we have 1 pair (Adam/Eve) of 0 months of age.
For the second or any subsequent row/month:
- Number of children (0th Column) will be same as number of adults (age > 0) in the previous month since all of them will produce 1 breed each. See the blue box and arrow above.
- All other column values will be same as the value of the previous row and previous column — since all of them will be one month older. See the green arrows above.
- Notice that we don't need to keep track of old population (age = 2), since they will die and will not be available in the next month.
The Code
Any questions — leave a comment. I will be glad to help!
