Rabbits and Recurrence Relations (Rosalind | English)

     

Hi everyone, how are you? In this time, I want to discuss about a problem from rosalind.info's web. The title is "Rabbits and Recurrence Relations". For the reference, you can first check out the problem what will be discussed (here). 

Overview

In this problem we will given 2 integers representing "the duration (in month)" and "number of couple of rabbits would be produce each month"; let's say those numbers are n and k. Our job is to finding the total number of couple of rabbits at the n-th month. 

The image above is an analogy of the rabbit population growth.  

For finding the answer of this problem, as the problem maker suggested, we can do with the dynamic programming approach. In this case, I want to use dynamic programming with 2 rows and n columns: the row 1 is representing the number of adult rabbit couples (who could produces offsprings) and the row 2 is representing the number of little rabbit couples (who couldn't produces offsprings); while the column (1 to n) is representing the number of months. The more the column shift to the right what would happen is: a couple adult rabbit produce k couples of offspring, and the little rabbits become adult. 

The answer (the total rabbit population) is located at the end of each row: The end of the row 1 is representing the total of adult rabbit couples, and the end of the row 2 is representing the total of little rabbit couples. 

The Code 

This is the code for solving this problem (with java language): 

static void solve() {

int n = ni();

int k = ni();

long[][] dp = new long[2][n];

dp[0][0] = 0;

dp[1][0] = 1;

for (int i = 1; i < n; i++) {

dp[0][i] = dp[0][i - 1] + dp[1][i - 1];

dp[1][i] = dp[0][i - 1] * k;

}

out.println(dp[1][n - 1] + dp[0][n - 1]);

}  

Input and Output

In the code above, I used ni() function for entering the integer-form data. That function is a extend from one of the input systems which are available in java, called BufferedReader. 

And for the output I used function out.println(). That function is modification from function System.out.println() which is very familiar in java. You can see the additional code for that modification (input and output) in my complete code at github. 

That's from me. If you want to ask something, you can write it in the comment section below. I hope this article is useful and see you in the next article! 

Reference :

Source of image 1 :https://www.facebook.com/ProjectRosalind/

Source of image 2 :https://medium.com/algorithms-for-life/rosalind-walkthrough-rabbits-and-recurrence-relations-4812c0c2ddb3