从递归到动态规划

如果一个算法可以拆成递归求解，那么它就基本可以使用动态规划求解

动态规划的本质就是缓存之前递归的结果，不让一些小的递归反复执行

1. 找递推关系式 & 终止条件

对于有递归关系的问题，首先找出递推关系式，比如斐波那契数列 (下标从 0 开始), 递推关系式如下

\[f(n)=f(n−1)+f(n−2)\]

其中 n≥2 (下标从 0 开始), 终止条件就是 n<2 且有

\[f(0)=f(1)=1\]

2. 写出递归函数

int func(int n)
{
  if (n < 2)
  {
    return 1;
  }
  else
  {
    return func(n - 1) + func(n - 2);
  }
}

3. 创建状态转移矩阵

若递归函数有 n 个参数，则定义 n 维数组，数组下标就是参数的取值， 数组中的值就是递归函数的返回值

4. 填写转移矩阵

• 填边界：将初始已知的值填入矩阵
• 矩阵其它位置：根据转移方程依次填写

5. 注意

并不是所有的递归都可以转换为矩阵形式，比如当参数个数过多时， 每个参数按照所有可能展开可能形成非常巨大的多维矩阵， 此时可以考虑递归的基础上剪枝，添加缓存等方式加快递归搜索性能