动态规划：用空间代替重复计算。
有些递归在展开计算时，总是重复调用一个子问题的解，这种重复调用的递归变成动态规划很有收益。
如果每次展开都是不同的解，或者重复调用的现象很少，那么没有改动态规划的必要。
任何动态规划问题都一定对应着一个重复调用行为的递归。
所以任何动态规划的题目都一定可以从递归入手，逐渐实现动态规划的方法。
例题一：斐波那契数
题目链接
实际难度：\(\color{F39C11}{{普及-}}\)
考察知识点
- 动态规划 - 线性DP
思路分析（递归）
由斐波那契数列：\(f_i= \begin{cases} 0,&i=0\\ 1,&i=1\\ f_{i-2}+f_{i-1}, &i \ge 2 \end{cases}\) 可得，对于每一个 \(f_i(i \ge 2)\)，只需要求出 \(f_{i-1}\) 和 \(f_{i-2}\) 即可。
如图所示：
即可求出 \(f_3\) 的值。
复杂度分析（递归）
时间复杂度
\[\begin{aligned}
T(n)&=\underbrace{T(n-1)+T(n-2)}_{递归}\\
&=O(2^n)
\end{aligned}
\]
空间复杂度
- 主要存储：\(O(n)\)
- 临时变量：\(O(1)\)
- 总空间：\(O(n)\)
C++代码
// Problem: 509. 斐波那契数
// Contest: LeetCode
// URL: https://leetcode.cn/problems/fibonacci-number/
//
// Powered by CP Editor (https://cpeditor.org)// 定义一个名为Solution的类，用于封装斐波那契数的求解方法
class Solution {
// 公有成员区域，表明以下函数可以被类外部调用
public:// 定义一个递归辅助函数f，参数i为需要计算的斐波那契数的索引，返回值为对应的斐波那契数int f(int i){// 递归终止条件1：当索引i为0时，根据斐波那契数定义，返回0if(i==0) return 0;// 递归终止条件2：当索引i为1时，根据斐波那契数定义，返回1if(i==1) return 1;// 递归计算：第i个斐波那契数等于第i-1个与第i-2个斐波那契数之和，返回计算结果return f(i-1)+f(i-2);}// 定义LeetCode要求的接口函数fib，参数n为目标斐波那契数的索引，返回对应的斐波那契数int fib(int n) {// 调用辅助函数f计算第n个斐波那契数，并返回结果return f(n);}
};