C语言/C++——递归、递推、动态规划

什么是动态规划：给定一个问题，我们把他拆成一个个子问题，直到子问题可以直接解决。然后把子问题的答案保存起来，以减少重复计算。再根据子问题的答案反推，得出原问题解的一种方法

递归的过程："递"的过程是分解子问题的过程；（dfs是第归的一种）

                        “归”的过程是产生答案的过程

“递”的过程是自顶向下，

“归”的过程是自底向上，“底”代表的是已知最小子问题的答案

递归适用于以下情况：

1.  问题具有递归结构：问题可以自然地分解为更小的子问题，且子问题具有相同的结构，即即原问题可以通过解决一个或多个更小规模的同类问题来解决。 

2.  递归基和递归步骤清晰：可以明确地定义递归的终止条件和分解方式。  

3.  问题规模适中：递归深度不会过大，避免栈溢出。  

4.  代码可读性优先：递归实现更简洁，且性能优化可以通过记忆化等方式实现。

递归与栈有些相似：后进的先出，先进的后出

递归通常需要满足以下两个条件：（递归的本质就是：由已知推未知））

1.  递归基（Base Case）：问题的最简单形式，可以直接求解，不需要进一步递归。递归基是递归的终止条件，防止无限递归。  

递归终止条件指的在程序中能实现return语句的条件

2.  递归步骤（Recursive Step）：将原问题分解为更小规模的子问题，并通过递归调用自身来解决这些子问题。

递推：是递归的“归”的过程

递归与递推的联系：递推公式 = dfs向下递归的公式

递推数组的初始值 = 递归的边界

记忆化搜索=暴力dfs+记录答案（拿空间换时间）

最暴力的dfs——>记忆化搜素——>递推。

例题1

一个楼梯共有 n 级台阶，每次可以走一级或者两级，问从第 0 级台阶走到第 n 级台阶一共有多少种方案。

输入格式

共一行，包含一个整数 n。

输出格式

共一行，包含一个整数，表示方案数。

数据范围

1≤n≤41

样例

输入  10          输出  89
输入  19          输出  6765
输入  35          输出  14930352

此题本质就是斐波那契数列

long long可存下第101项

代码一（dfs暴力搜索,此法在n>41时，时间超限）(时间复杂度O())

#include<iostream>    
#include<algorithm>   
#include<cstring>     

using namespace std;  // 使用标准命名空间
using i64 = long long; // 定义一个别名i64，表示64位整数类型

int n;                 // 定义全局变量n，表示输入的斐波那契数列的索引

// 定义递归函数dfs，用于计算斐波那契数列的第x项
i64 dfs(int x)
{
    if(x == 1) return 1;                // 斐波那契数列的第1项为1，递归结束标志
    else if(x == 2) return 2;           // 斐波那契数列的第2项为2,递归结束标志
    else return dfs(x - 1) + dfs(x - 2); // 递归计算：第x项等于第x-1项与第x-2项之和
                                         // 深度优先搜索：先递归计算dfs(x-1)，再计算dfs(x-2)
//直到搜索到x=1或x=2返回，在递推期间不返回答案
}

int main()
{
    cin >> n;                           // 从标准输入读取一个整数n
    i64 ans = dfs(n);                   // 调用dfs函数计算斐波那契数列的第n项
    cout << ans << endl;                // 输出结果
    return 0;                           // 程序正常结束
}

 代码二（dfs记忆化搜索）优化时间复杂度，记忆数组为全局变量，须达到数组索引相同值相同

#include<iostream>    // 包含输入输出流库
#include<algorithm>   // 包含算法库（虽然本代码未使用其中的算法）
#include<cstring>     // 包含字符串操作库（虽然本代码未使用其中的函数）

using namespace std;  // 使用标准命名空间
using i64 = long long; // 定义一个别名i64，表示64位long long 整数类型
const int N = 100;     // 定义一个常量N，表示记忆化数组的最大大小

int n;                 // 定义全局变量n，表示输入的斐波那契数列的索引
i64 mem[N];            // 定义一个全局数组mem，用于记忆化存储斐波那契数列的结果

// 定义递归函数dfs，用于计算斐波那契数列的第x项
int dfs(int x)
{
    if(mem[x]) return mem[x]; // 第二次计算第x项时，直接返回其值（记忆化）

    i64 sum = 0;              // 定义一个变量sum，用于存储计算结果
    if(x == 1) sum = 1;       // 斐波那契数列的第1项为1，递归结束条件
    else if(x == 2) sum = 2;  // 斐波那契数列的第2项为2，递归结束条件
                                //递归结束条件是指的是能实现return语句的条件
    else sum = dfs(x - 1) + dfs(x - 2); // 递归计算：第x项等于第x-1项与第x-2项之和
                                //递归调用语句之前每次调用都是必须要执行的，递推语句之后的，在 
                      //调用结束之后，才开始执行，此后语句的执行顺序同栈，最后一次调用的最先执行

    mem[x] = sum;             // 将第x项结果存储到mem[x]中，在第一次深度搜索时将完整的执行所有                    
                              //调用语句
    return sum;               // 返回计算结果
}

int main()
{
    scanf("%d", &n);          // 从标准输入读取一个整数n
    i64 answer = dfs(n);      // 调用dfs函数计算斐波那契数列的第n项
    printf("%lld\n", answer); // 输出结果
    return 0;                 // 程序正常结束
}

代码思路分析

1. 斐波那契数列的定义
   斐波那契数列是一个经典的数列，定义如下：

   • F(1)=1

   • F(2)=2

   • F(n)=F(n−1)+F(n−2) （对于 n>2）

   本代码中，斐波那契数列的第1项为1，第2项为2，之后的每一项都是前两项的和。

2. 递归实现
   代码通过递归函数dfs来计算斐波那契数列的第x项：

   • 如果x为1或2，直接返回1或2（递归终止条件）。

   • 否则，通过dfs(x-1) + dfs(x-2)递归计算第x项的值。

3. 记忆化搜索（Memoization）
   为了避免递归过程中的重复计算，代码引入了一个数组mem来存储已经计算过的斐波那契数列的结果。

   • 在dfs函数中，如果mem[x]已经存储了值，则直接返回mem[x]，避免重复计算。

   • 如果mem[x]未存储值，则计算结果后将其存储到mem[x]中，供后续调用使用。

   记忆化搜索大大提高了递归的效率，将时间复杂度从指数级（O()）降低到线性级（O(n)）。

4. 主函数

   • 主函数从标准输入读取一个整数n，表示需要计算斐波那契数列的第n项。

   • 调用dfs(n)计算结果，并将结果存储到answer中。

   • 最后将结果输出到标准输出。

代码三（动态规划）

使用迭代方法计算斐波那契数列，避免递归调用。 模拟递归的“归” 

#include<iostream>    // 包含输入输出流库
using namespace std;  // 使用标准命名空间
using i64 = long long; // 定义一个别名i64，表示64位整数类型

const int N = 100;    // 定义一个常量N，表示数组dp的最大大小
i64 dp[N] = {0};      // 定义一个数组dp，用于存储斐波那契数列的值，并初始化为0

int main()
{
    int n;            // 定义一个变量n，表示输入的斐波那契数列的索引
    cin >> n;         // 从标准输入读取一个整数n
    dp[1] = 1;        // 初始化dp数组的第1项为1
    dp[2] = 2;        // 初始化dp数组的第2项为2
    for(int i = 3; i <= n; i++) // 从第3项开始，依次计算斐波那契数列的值
    {
        dp[i] = dp[i - 1] + dp[i - 2]; // 第i项等于第i-1项与第i-2项之和
    }
    cout << dp[n] << endl; // 输出斐波那契数列的第n项
    return 0;              // 程序正常结束
}

代码功能说明

1. 斐波那契数列的动态规划实现：

   • 使用一个数组dp来存储斐波那契数列的值，避免了递归实现中的重复计算问题。

   • 初始化dp[1]为1，dp[2]为2。

   • 通过循环，从第3项开始，依次计算斐波那契数列的值，直到第n项。

2. 主函数：

   • 从标准输入读取一个整数n，表示需要计算斐波那契数列的第n项。

   • 使用动态规划的方法计算斐波那契数列的第n项，并将结果存储在dp[n]中。

   • 将结果输出到标准输出。

代码四 优化空间复杂度

如果只需要计算第n项，可以只存储前两项的值，从而将空间复杂度优化到O(1)。

#include<iostream>    // 包含输入输出流库
using namespace std;  // 使用标准命名空间
using i64 = long long; // 定义一个别名i64，表示64位整数类型

int main()
{
    int n;            // 定义一个变量n，表示输入的斐波那契数列的索引
    cin >> n;         // 从标准输入读取一个整数n

    i64 a = 1, b = 2, c; // 定义三个变量：
                         // a表示斐波那契数列的第1项（F(1) = 1）
                         // b表示斐波那契数列的第2项（F(2) = 2）
                         // c用于存储当前计算的斐波那契数列的第i项

    // 特殊情况处理：直接输出F(1)或F(2)
    if(n == 1) cout << a << endl;  // 如果n为1，直接输出第1项（1）
    else if(n == 2) cout << b << endl; // 如果n为2，直接输出第2项（2）
    else
    {
        // 从第3项开始计算斐波那契数列
        for(int i = 3; i <= n; i++) // 循环计算从第3项到第n项
        {
            c = a + b;  // 当前项c等于前两项a和b的和
            a = b;      // 更新a为b（即F(i-2) = F(i-1)）
            b = c;      // 更新b为c（即F(i-1) = F(i)）
        }
        cout << c << endl; // 输出计算得到的第n项
    }
    return 0;              // 程序正常结束
}