Rabbits give birth to rabbits

Classic problem: every month since 3 months gives birth to a pair of rabbits, every month after rabbit child grows to the 3rd month gives birth to a pair of rabbits again, if rabbit is deathless, how many is the total number of rabbits that asks every month? The number of rabbits per month is the total number of rabbits per month. Assuming the rabbit can be divided into three kinds, in small rabbit from each month after three months after birth will give birth to a pair of rabbits, then we assume that the first month of small rabbit rabbit, in the second month of the rabbit, after 3 months of big rabbit, so the first month respectively are 1, 0, 0, 0, 1, 0, respectively the second month, 3 months respectively 1, 0, 1, The fourth month is,1,1,1; the fifth month is, 2,1, 2; the sixth month is, 3, 2, 3; the seventh month is, 5, 3, 5… The total number of rabbits is: 1, 1, 2, 3, 5, 8, 13…… The result is a Fibonacci sequence in which, from the third month onwards, the total number of rabbits in the following months is equal to the sum of the total number of rabbits in the preceding two months.

Violent Iteration (Fibonacci sequence)

 public static int fib(int N) {
        if (N == 1 || N == 2) {
            return 1;
        }
        return fib(N - 1) + fib(N - 2);
    }
Copy the code
Disadvantages: there are a lot of repeated calculation, repeated calculation subset.

Take the memo

 public static int fib(int N) {
        if (N == 1 || N == 2) {
            return 1;
        }
        int arr[] = new int[20];
        arr[0] = arr[1] = 1;
        for (int i = 2; i < arr.length; i++) {
            arr[i] = arr[i - 1] + arr[i - 2];
        }
        return arr[N-1];

    }
Copy the code