常见算法介绍 ---- 动态规划算法介绍（C++描述）

常见算法介绍 ---- 动态规划算法介绍（C++描述）

壹、【算法简介】

        动态规划法(Dynamic Programming Algorithm，简称DPA)类似于分治法，用于研究多阶段决策过程的优化过程与求得一个问题的最优解。

        关于分治法：分治法（Divide and Conquer）常用来逐一拆解复杂的问题，核心思想就是将一个难以直接解决的大问题依照相同的概念分割成两个或更多的子问题，以便各个击破。

贰、【基本方法】
        动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。
        与分治方法不同的是，动态规划可以将每个子问题的答案记录下来，以供下次计算的时候直接取用。优点是可以减少再次计算的时间，而且可以将这些解组合成大问题的解。使用动态规划可以解决重复计算的问题。

叁、【示例代码】

        对于前面的[递归算法]小节讲的斐波那契数列，它每次循环过程中，都要将已经计算过的内容重新计算一遍，非常耗时，效率不高。详见：常见算法介绍 ---- 递归算法介绍（C++描述）_碧波bibo的博客-CSDN博客

        我们可以进一步优化：将每次的计算结果储存在一个数组中，下次循环的时候直接拿过来用，避免重复计算。

        下面的代码请仔细体会，一定要仔细体会，对于初学者，我写的注释也请一定要看：

#include 
using namespace std;
int Fib(int);
int main()
{
    
    cout << "Fib(10) = " << Fib(10) << endl;
    return 0;
}

int Fib(int n)
{
    static int record[999] = {0};  //这个数组用来记录每次计算的结果，
    static int result = 0;
    result = record[n];
    if (result == 0)  // 最开始的时候，n == 10；但是record[10] == 0;因此可以进入条件。再后面就进不去了
    {
        if (n == 0)
        {
            record[0] = 0;  // 1、在递归条件下，n == 0的时候会最开始计算，将计算结果储存在record[0]，备用
            return record[0];
        }
        else if (n == 1)
        {
            record[1] = 1; // 2、然后再计算 n == 1的情况，并将n == 1时候的计算结果储存在record[1]中，备用
            return record[1];
        }
        result = Fib(n - 1) + Fib(n - 2); // 3.0、当n == 2时，计算Fib(1)+Fib(0)，此时有record[1] == 0，record[0] == 1(此时不会进入16行条件)，通过第32行将计算结果放到record[2]备用
        // 3.1 当n == 3 时，计算Fib(2)+Fib(1)，此时都不会进入16行的条件，通过第32行将计算结果放到record[3]中备用
        // 3.2 当n == 4 时，计算Fib(3)+Fib(2)，此时都不会进入16行的条件，通过第32行将计算结果放到record[4]中备用
        // ...
        record[n] = result; // 3、在递归的时候，将先计算record[2],即先计算n == 1时的值，计算结果储存在record[2]中，备用
    }
    return result;
}

【示例输出】

Fib(10) = 55

【附】斐波那契数列的数学意义：