从斐波那契开始优化递归

斐波那契数列：1、1、2、3、5、8、13……

每一项都是前两项之和，要求第 n 项的结果就需要 ，那么能不能做进一步优化呢？

对于类似斐波那契数列这样的，除了初始项之外，后续每一项都严格满足某一递归式的问题，都能优化为 。

什么是严格满足？就像斐波那契数列一样，除了 1、2 以外其他项都满足 。如果一个递归是按照不同的条件进行不同的递归，就不是一个严格满足某一递归式，就不一定能优化为 ，例如下面的代码就不是严格满足：

int getMin(int a, int b, int c) {
    int data = 0;
    if (a > 2) {
        data = getMin(10, 3, 5);
    } else if  (c > 2) {
        data = getMin(2, 3, 45);
    } else {
        data = -1;
    }
    return data;
}

也可以这样理解：只要是有递归式的就是严格满足的。如某个问题的解存在如下递归式：，只要后续项都满足该递归式，那么就能被优化为

以斐波那契数列为例：，是一个二阶行列式问题，则一定存在通用式：
上面的同时是线性代数的知识，有兴趣可以去看看……

将数列带入，就可以得到


进一步得出：

通过计算得出

则可以得到斐波那契数列的递归式：

这样一来，就将第 N 项问题转化为了一个矩阵的 N 次方问题，矩阵的 N 次方算的越快求解就越快

如果对于随便一个数，该数的 N 次方证明算最快呢？

假设求 ，如果使用 10 * 10 75 次就能求出，复杂度为 。
优化为 复杂度：75 的 二进制位 1001011，即，进行如下运算：

• ，二进制上第 1 位为 1，进行计算
• ，二进制上第 2 位为 1，进行计算
• ，二进制上第 3 位为 0，不进行计算
• ，二进制上第 4 位为 1，进行计算
• ，二进制上第 5 位为 0，不进行计算
• ，二进制上第 6 位为 0，不进行计算
• ，二进制上第 7 位为 1，进行计算

即： ，通过 7 次计算即可得出

总体思路：先将指数变为二进制，然后通过二进制的每一位来判断是否需要将该次幂进行计算，通过二进制的长度次计算即可得到。如：，通过 5 次计算就能得到结果。

同样的方法求一个矩阵的幂 只需要求出 、、、、、、 即可然后判断 75 对应的二进制位上是否是 1 ，再乘上单位矩阵即可。

斐波那契数列实现：

public class Fibonacci {

    private static int fi(int n) {
        if (n <= 0) return -1;

        if (n == 1 || n == 2) return 1;

        int[][] base = {
                {1, 1},
                {1, 0}
        };

        int[][] res = matrixPower(base, n - 2);

        return res[0][0] + res[0][1];
    }

    private static int[][] matrixPower(int[][] m, int p) {
        int[][] res = new int[m.length][m[0].length];

        // 单位矩阵
        for (int i = 0; i < m.length; i++) {
            res[i][i] = 1;
        }

        int[][] tmp = m;
        for (; p != 0; p >>= 1) {
            if ((p & 1) == 1) {
                res = muliMatrix(res, tmp);
            }
            tmp = muliMatrix(tmp, tmp);
        }

        return res;
    }

    // 矩阵相乘
    private static int[][] muliMatrix(int[][] m1, int[][] m2) {
        int[][] res = new int[m1.length][m2[0].length];
        for (int i = 0; i < m1.length; i++) {
            for (int j = 0; j < m2[0].length; j++) {
                for (int k = 0; k < m2.length; k++) {
                    res[i][j] += m1[i][k] * m2[k][j];
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        for (int i = 1; i < 30; i++) {
            System.out.println(fi(i));
        }
    }
}

再来看一个比较复杂的：，最少需要前面 5 项才能得到后续结果，这是个 5 接行列式通用式为：
，可以用同样的方式来优化时间复杂度。

具体例子：
农场对种牛的生育进行控制，农场一开始只有一只种牛，每年每只种牛都能生一只小种牛，小种牛需要 3 年后才能生新的种牛，请问，第 N 年农场有多少只种牛？

• 第一年，只有A， 共 1 只
• 第二年，A 生 B， 共 2 只
• 第三年，A 生 C，现在有种牛 A、B、C 共 3 只
• 第四年，A 生 D，现在有种牛 A、B、C 、D共 4 只
• 第五年，A 生 E、B 生 F，现在有种牛 A、B、C 、D、E、F 共 6 只
• 第六年，A 生 G、B 生 H、C 生 I，现在有种牛 A、B、C 、D、E、F、G、H、I 共 9 只
• ……
• 第 N 年，

例子：达标字符串

字符串只由 ‘0’ 和 ‘1’ 两种字符构成
当字符串长度为 1 时，所有可能的字符串为 “0”、”1”；
当字符串长度为 2 时，所有可能的字符串为 “00”、”01”、”10”、”11”；
当字符串长度为 3 时，所有可能的字符串为 “000”、”001”、”010”、”011”、”100”、”101”、”110”、”111”……
如果某一个字符串中，只要是出现 ‘0’ 的位置，左边就靠着 ‘1’，这样的字符串叫作达标字符串。
给定一个正数 N，返回所有长度为 N 的字符串中，达标字符串的数量。
比如，N=3，返回 3，因为只有 “101”、”110”、”111” 达标。

思路一：
递归每个位置都有可能是 0、1 然后判断组成字符串是否合法

public static int getNum1(int n) {
    return process(n, "");
}

private static int process(int n, String str) {
    if (n == 0) {
        return check(str) ? 1 : 0;
    }

    return process(n - 1, str + "0") + process(n - 1, str + "1");
}

private static boolean check(String str) {
    char[] chars = str.toCharArray();
    if (chars[0] == '0') return false;
    for (int i = 1; i < chars.length; i++) {
        if (chars[i] == '0' && chars[i - 1] == '0') return false;
    }
    return true;
}

思路二：
递归改动态规划

public static int getNum2(int n) {
    if (n < 1) return -1;
    if (n == 1) return 1;
    if (n == 2) return 2;

    int[] dp = new int[n];
    dp[0] = 1;
    dp[1] = 2;

    for (int i = 2; i < n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n - 1];
}

思路三：
打表法

public static int getNum3(int n) {
    if (n < 1) return -1;
    if (n == 1) return 1;
    if (n == 2) return 2;

    int first = 1;
    int second = 2;

    int res = 0;
    for (int i = 2; i < n; i++) {
        res = first;
        first = second;
        res += first;
        second = res;
    }

    return res;
}

思路四：
矩阵行列式规律

public static int getNum4(int n) {
    if (n < 1) {
        return 0;
    }
    if (n == 1 || n == 2) {
        return n;
    }
    int[][] base = {{1, 1}, {1, 0}};
    int[][] res = matrixPower(base, n - 2);
    return 2 * res[0][0] + res[1][0];
}

public static int[][] matrixPower(int[][] m, int p) {
    int[][] res = new int[m.length][m[0].length];
    for (int i = 0; i < res.length; i++) {
        res[i][i] = 1;
    }
    int[][] tmp = m;
    for (; p != 0; p >>= 1) {
        if ((p & 1) != 0) {
            res = muliMatrix(res, tmp);
        }
        tmp = muliMatrix(tmp, tmp);
    }
    return res;
}

public static int[][] muliMatrix(int[][] m1, int[][] m2) {
    int[][] res = new int[m1.length][m2[0].length];
    for (int i = 0; i < m1.length; i++) {
        for (int j = 0; j < m2[0].length; j++) {
            for (int k = 0; k < m2.length; k++) {
                res[i][j] += m1[i][k] * m2[k][j];
            }
        }
    }
    return res;
}