Hibernate animals proliferation

Problem:

　　There is a kind of unicellular organism, it starts to generate one offspring per day on the 5th day after birth, and it starts to hiberate on the 9th day after birth. Now suppose the starting date is day 1 and there is one such new born animal, what is the number of the animals on the nth day?

We should maintain a data structure to count the number of animals based on their ages and set up the state transfer function:

　　Define function counter(a, d) to denote the number of animals that are on their ath day after birth on day d. Since animals are inactive from the 9th day after birth, all animals that are 9 or more days old are marked 9 days old.  

　　At the beginning, 

　　counter(1, 1)=1

　　counter(2, 1)=0

　　counter(3, 1)=0

　　counter(4, 1)=0

　　counter(5, 1)=0

　　counter(6, 1)=0

　　counter(7, 1)=0

　　counter(8, 1)=0

　　counter(9, 1)=0

　　At day d the following equations hold:

　　counter(1, d)=counter(4, d-1)+counter(5, d-1)+counter(6, d-1)+counter(7, d-1)

　　counter(2, d)=counter(1, d-1)

　　counter(3, d)=counter(2, d-1)

　　counter(4, d)=counter(3, d-1)

　　counter(5, d)=counter(4, d-1)

　　counter(6, d)=counter(5, d-1)

　　counter(7, d)=counter(6, d-1)

　　counter(8, d)=counter(7, d-1)

　　counter(9, d)=counter(8, d-1)+counter(9, d-1)

Then we can accumulate number of animals and get the final result.

Code:

public static int proliferation(int day) {
    int[] prev= {1,0,0,0,0,0,0,0,0};
    int[] cur=new int[9];
    
    int i=1;
    while(i<day) {
        for(int j=0;j<9;j++) {
            switch(j) {
                case 0:{
                    cur[j]=prev[3]+prev[4]+prev[5]+prev[6];
                } break;
                case 8:{
                    cur[j]=prev[7]+prev[8];
                } break;
                default:{
                    cur[j]=prev[j-1];
                } break;
            }
        }
        prev=cur;
        cur=new int[9];
        i++;
    }
    
    int res=0;
    for(int j=0;j<9;j++)
        res+=prev[j];
    return res;
}

Note there exists a O(log n) algorithm which applies matrix multiplication.

Hibernate animals proliferation

原文：https://www.cnblogs.com/shepherdgai/p/13616507.html