算法-动态规划之斐波那契数列｜默然的博客

参考

labuladong的算法小抄的动态规划解题套路框架,作者写的很好，所以下文中有些描述会直接拿过来（斜体标注）

什么是动态规划

通过将原问题分解为若干个相对简单的子问题，通过求解子问题的方式求解原来复杂问题的方法叫动态规划。动态规划问题一般是求最值。所以求解动态规划的核心是穷举，即将所有结果穷举出来进而选出最优解。

动态规划三要素

首先，动态规划的穷举有点特别，因为这类问题存在 「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要 「备忘录」 或者 「DP table」 来优化穷举过程，避免不必要的计算。

而且，动态规划问题一定会具备 「最优子结构」，才能通过子问题的最值得到原问题的最值。

另外，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出正确的 「状态转移方程」 才能正确地穷举。

问题描述

Leetcode 509. 斐波那契数

暴力解法

public int Fib(int N)
{
    if (N == 0) return 0;
    else if (N == 1 || N == 2) return 1;
    else
        return Fib(N - 1) + Fib(N - 2);
}

这种写法应该老师都讲过，但是这种写法效率挺低，且看，如果计算fib(30):

fib(30)=fib(29)+fib(28)
fib(29)=fib(28)+fib(27)     //重复计算了fib(28)
fib(28)=fib(27)+fib(26)     //重复计算了fib(27)
...
fib(3)=fib(2)+fib(1)

在这个过程中做了大量重复的工作，其时间复杂度达到了O(2^n^)，这就是：重叠子问题，解决点重叠子问题就可提高代码效率：

带备忘录的递归解法

已上面为例，从f(3)~f(28)，每个都被计算两遍，那么可以通过创建一个备忘录的数组去保存计算的结果，如果下次再用到直接从备忘录里拿就可以了，这就实现了使用内存换时间，代码如下：

public int Fib(int N)
{
    if (N == 0) return 0;
    else if (N == 1 || N == 2) return 1;
    //备忘录，大小为N+1
    int[] map = new int[N+1];
    map[1] = 1;
    map[2] = 1;
    return dp(map,N);
}
public int dp(int[] map, int N)
{
    if (map[N] != 0) return map[N];
    else
    {
        map[N] = dp(map,N - 1) + dp(map,N - 2);
        return map[N];
    }
}

自底向上

上面两种通过递归的形式将大问题拆分为小问题进而对小问题求解最终实现解决原问题。当然也可以通过小问题去推导大问题，这样就不用一步步递归,一次循环就可求解，如下用for循环求解Fib：

public int Fib(int N)
{
    if (N == 0) return 0;
    else if (N == 1 || N == 2) return 1;

    int pre = 1;
    int current = 1;
    int sum = -1;
    for (int i = 3; i <= N; i++)
    {
        sum = pre + current;
        pre = current;
        current = sum;
    }
    return current;
}

相关阅读

• 分治算法解决问题再回顾
• 算法-从第一个元素开始，计算累和的最大值