斐波那契数相关

结合动态规划分治、避免重叠子问题的思想来进行求解

剑指 Offer 10- I，II

两个问题都与斐波那契数列相关，以I为例，斐波那契数列可以通过递归实现，但要避免大量重复的运算，因此可以使用数组暂存。（自己写的就是丑陋了些）

    public static int fib(int n) {
        int[] res = new int[n+1];

        return fibHepler(n,res);
    }

    private static int fibHepler(int n,int[] res){
        if(n<=1) {
            res[n] = n;
            return n;
        }
        else {
            res[n-1] = res[n-1]!=0?res[n-1]:fibHepler(n-1,res);
            res[n-2] = res[n-2]!=0?res[n-2]:fibHepler(n-2,res);
            return res[n-1]+res[n-2];
        }
    }

其实可以避免递归

    int[] res = new int[n+1];
    res[0] = 0;
    res[1] = 1;

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

而通过推公式f(n) = f(n-1) + f(n -2) >> f(n+1) = f(n) + f(n-1)可以进一步简化问题。关键在于如何写来避免特殊情况。

        int a = 0, b = 1, sum;
        for(int i = 0; i < n; i++){
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;

引用

图解算法数据结构 - LeetBook - 力扣（LeetCode）全球极客挚爱的技术成长平台