什么是动态规划：给定一个问题，我们把他拆成一个个子问题，直到子问题可以直接解决。然后把子问题的答案保存起来，以减少重复计算。再根据子问题的答案反推，得出原问题解的一种方法
递归的过程："递"的过程是分解子问题的过程；（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; // 程序正常结束
}代码思路分析
斐波那契数列的定义
斐波那契数列是一个经典的数列，定义如下：
F(1)=1
F(2)=2
F(n)=F(n−1)+F(n−2) （对于 n>2）
本代码中，斐波那契数列的第1项为1，第2项为2，之后的每一项都是前两项的和。
递归实现
代码通过递归函数dfs来计算斐波那契数列的第x项：
如果
x为1或2，直接返回1或2（递归终止条件）。否则，通过
dfs(x-1) + dfs(x-2)递归计算第x项的值。记忆化搜索（Memoization）
为了避免递归过程中的重复计算，代码引入了一个数组mem来存储已经计算过的斐波那契数列的结果。
在
dfs函数中，如果mem[x]已经存储了值，则直接返回mem[x]，避免重复计算。如果
mem[x]未存储值，则计算结果后将其存储到mem[x]中，供后续调用使用。记忆化搜索大大提高了递归的效率，将时间复杂度从指数级（O(
)）降低到线性级（O(n)）。
主函数
主函数从标准输入读取一个整数
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; // 程序正常结束
}代码功能说明
斐波那契数列的动态规划实现：
使用一个数组
dp来存储斐波那契数列的值，避免了递归实现中的重复计算问题。初始化
dp[1]为1，dp[2]为2。通过循环，从第3项开始，依次计算斐波那契数列的值，直到第
n项。主函数：
从标准输入读取一个整数
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; // 程序正常结束
}