攻略dp(动态规划攻略：如何计算斐波那契数列)

什么是动态规划？

动态规划（DP）是一种算法思想，用于解决一类最优化问题。DP通常用于求解最优解，避免重复计算，有利于提升算法效率。

什么是斐波那契数列？

斐波那契数列是指数列第n项及后一项之和，其公式为：F(n)=F(n-1)+F(n-2)

例如，斐波那契数列的前10项为：0, 1, 1, 2, 3, 5, 8, 13, 21, 34。

斐波那契数列的常见问题

在计算斐波那契数列时，常见问题包括：

如何计算第n项斐波那契数？

如何计算前n项斐波那契数？

如何计算斐波那契数列的最大值或最小值？

斐波那契数列的暴力算法

最直接的方式是使用递归或循环的暴力算法来计算斐波那契数列。

int fib(int n) {

    if (n == 0 || n == 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

然而，这种算法时间复杂度为O(2^n)，因为在计算F(n)之前，需要计算F(n-1)和F(n-2)，而在计算F(n-1)和F(n-2)时，还需要计算F(n-2)和F(n-3)，以此类推。

斐波那契数列的DP算法

从斐波那契数列的暴力算法中可知，许多重复计算是不必要的，因此，我们可以使用DP算法来优化斐波那契数列的计算。

DP算法的基本思想是将一个大问题分解成小问题并解决，同时将子问题的解缓存以避免重复计算。

使用DP算法可以将斐波那契数列的时间复杂度降至O(n)。

int fib(int n) {

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

斐波那契数列的DP优化

通过分析DP算法的执行流程可以发现，我们只需要记录F(n-1)和F(n-2)的值就可以了，不必缓存所有的F(0)~F(n)。

int fib(int n) {

    if (n == 0 || n == 1) {
        return n;
    }
    int pre1 = 0, pre2 = 1;
    int cur = 0;
    for (int i = 2; i <= n; i++) {
        cur = pre1 + pre2;
        pre1 = pre2;
        pre2 = cur;
    }
    return cur;
}

总结

动态规划（DP）是一种算法思想，使用DP算法可以优化斐波那契数列的计算，并将时间复杂度降至O(n)。DP算法的基本思想是将一个大问题分解成小问题并解决，同时将子问题的解缓存以避免重复计算。