• 有些递归在展开计算时，总是重复调用同一个子问题的解，这种重复调用的递归变成动态规划很有收益

• 如果每次展开都是不同的解，或者重复调用的现象很少，那么没有改动态递归的必要

• 任何动态规划问题都一定对应着一个有重复调用行为的递归

• 所以任何动态规划的题目都一定可以从递归入手，逐渐实现动态规划的方法

• 从尝试入手（暴力递归），逐渐改造成动态规划，因为好写，而且一旦发现错误好改！！

题目1：斐波那契数

• 斐波那契数（通常用表示）形成的序列称为斐波那契数列，该数列由和开始，后面的每一项数字都是前面两项数字的和，也就是：其中 给定，计算

• 斐波那契数问题最经典，这里采用的方法时间复杂度为 但是最优解来自矩阵快速幂，时间复杂度可以做到，在后面会讲到

1. 暴力递归：
• 时间复杂度分析：为，例如要求时的斐波那契数，相当于要展开层，树高为；
• 时间复杂度差的原因：有很多重复计算！ 例如，要求，那么需要先知道和，先到左侧展开求，又需要知道和，那么再次到右边去求，相当于进行了重复计算！
• 解决方法：使用“缓存表”，即用一张表记录已经计算出来得到的那些结果，下次在递归时需要参数的时候，先检查表内是否有需要的参数，如果有就直接返回，不要去递归了；否则就先递归求出结果，然后将其加到缓存表中。
• 从顶到底的动态规划，又叫记忆化搜索; 这种方法相比下面的从底到顶的方法更通用一点；
• 从底到顶的动态规划：滑动窗口，需要先分析递归调用依赖

题目2：最低票价

题目描述

• 在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行；在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出，每一项是一个从 1 到 365 的整数

• 火车票有三种不同的销售方式：
• 一张 为期 天 的通行证售价为 cost[0] 美元；
• 一张 为期 天 的通行证售价为 cost[1] 美元；
• 一张 为期 天 的通行证售价为 cost[2] 美元

• 通行证允许数天无限制的旅行；例如，如果我们在第 天获得一张为期 天的通行证，那么我们可以连着旅行 天（第 天）

• 返回 你想要完成在给定的列表 days 中列出的每一天旅行所需要的最低消费。

• 测试链接：983. 最低票价 - 力扣（LeetCode）

1.暴力递归

2.从顶到底的动态规划

3.从底到顶的动态规划

• 要点是要分析递归结构

题目3：解码方法

1.暴力递归

2.从顶到底的动态规划

3.从底到顶的动态规划

4.从底到顶的动态规划+空间压缩