基础 DP

斐波那契数列

斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

即：

• a_n = 1 (n = 1 or n = 2)
• a_n = a_n-1
  • a_n-2 (n >= 3)

求斐波那契的第 n 项

递归

思路

找到了其中的 最优子结构（递归公式）：f(n) = f(n - 1) + f(n - 2)

实现

long long func(int n)
{
    if (n == 1 || n == 2) return 1;
    return func(n - 1) + func(n - 2);
}

复杂度 · O(2ⁿ)

优化

计算 f(n) 时要计算 f(n - 1) 和 f(n - 2)，而计算 f(n - 1) 要计算 f(n - 2) 和 f(n - 3)...因此有很多是重复计算，因此考虑到用空间换时间，记录下这些值，以后需要计算这些值的时候直接返回已经计算得到的值即可

空间换时间 · 记忆化

思路

发现有很多值重复计算，用空间换时间

实现

long long f[1001] = {0, 1, 1};
long long func(int n)
{
    if (!f[n]) f[n] = func(n - 1) + func(n - 2);
    return f[n];
}

复杂度 · O(n)

优化

不难发现，结果是从前往后一位一位计算得到的，第 3 位，第 4 位...第 n 位。而每次计算的时候只与这一位的前两位有关系，因此可以使用循环的方法完成。

递归变循环

思路

打印空间，发现是按顺序从前往后运行的

实现

long long f[10001] = {0, 1, 1};
long long func(int n)
{
    for (int i = 3; i <= n; i++) f[i] = f[i - 1] + f[i - 2];
    return f[n];
}

复杂度

• 时间复杂度 · O(n)

• 空间复杂度 · O(n)

优化

不难发现，当前值至于前两个值有关，因此不需要保留前两个之前的值

空间压缩 · 即用即抛

思路

发现很多空间被重复利用，每次计算只与前两项有关

实现

long long a = 1, b = 1, c;
long long func(int n)
{
    for (int i = 3; i <= n; i++)
    {
        c = b;
        b = a + b;
        a = c;
    }
    return b ;
}

• 时间复杂度 · O(n)

• 空间复杂度 · O(1)