登录以参加训练计划

我们经常会发现同样的一个问题会反复的出现、反复的出现，但又不是简单的重复执行。那怎么办呢？

递归递推的核心思路都是一致的，找到某个状态怎么来的 （ 递归 ），或者是某个状态可以去哪里 （递推）

状态就是问题参数化的过程，就是说，把问题里面变化的部分用参数提取出来，形成一个没有具体数字的问题。 （ 比如 n级台阶的走法，而不是3级、5级的走法 ； 又比如用v块钱买到最具攻击力的装备，而不是用100块买到的等等）。

然后找到这些参数从大到小 or 从小到大的关系，从而得出递归 or 递推公式。

优化

递归的过程中会出现重复计算的部分，我们可以引入记忆化策略，把算过的结果用数组存下来。 （ 一般来说，递归函数有$N$个参数，就需要一个$N$维数组来做结果保存 ）

递归 + 记忆化 对比 递推的优点

1. 好写 - 不用递推顺序、不用管初值
2. 自带剪枝 - 递推可能会存在搜索路径上不存在的状态的计算