例题一
解法（暴搜 -> 记忆化搜索 -> 动态规划）：
算法思路：
暴搜：
a.
递归含义：给 dfs
⼀个使命，给他⼀个数
n
，返回第
n
个斐波那契数的值；
b.
函数体：斐波那契数的递推公式；
c.
递归出⼝：当 n == 0
或者
n == 1
时，不⽤套公式。
记忆化搜索：
a.
加上⼀个备忘录；
b.
每次进⼊递归的时候，去备忘录⾥⾯看看；
c.
每次返回的时候，将结果加⼊到备忘录⾥⾯。
动态规划：
a.
递归含义 -> 状态表⽰；
b.
函数体 -> 状态转移⽅程；
c.
递归出⼝ -> 初始化。
法一：记忆化搜索
法二：动态规划
例题二
解法（暴搜 -> 记忆化搜索 -> 动态规划）：
算法思路：
暴搜：
a.
递归含义：给 dfs
⼀个使命，给他⼀个下标，返回从
[0, 0]
位置⾛到
[i, j]
位置⼀共有多少种⽅法；
b.
函数体：只要知道到达上⾯位置的⽅法数以及到达左边位置的⽅法数，然后累加起来即可；
c.
递归出⼝：当下标越界的时候返回 0
；当位于起点的时候，返回
1
。
记忆化搜索：
a.
加上⼀个备忘录；
b.
每次进⼊递归的时候，去备忘录⾥⾯看看；
c.
每次返回的时候，将结果加⼊到备忘录⾥⾯。
动态规划：
a.
递归含义 -> 状态表⽰；
b.
函数体 -> 状态转移⽅程；
c.
递归出⼝ -> 初始化。
方法一：记忆化搜索
方法二：动态规划
例题三
解法（暴搜 -> 记忆化搜索 -> 动态规划）：
算法思路：
暴搜：
a.
递归含义：给
dfs
⼀个使命，给他⼀个数
i
，返回以
i
位置为起点的最⻓递增⼦序列的⻓度；
b.
函数体：遍历 i
后⾯的所有位置，看看谁能加到
i
这个元素的后⾯。统计所有情况下的最⼤值。
c.
递归出⼝：因为我们是判断之后再进⼊递归的，因此没有出⼝~
记忆化搜索：
a.
加上⼀个备忘录；
b.
每次进⼊递归的时候，去备忘录⾥⾯看看；
c.
每次返回的时候，将结果加⼊到备忘录⾥⾯。
动态规划：
a.
递归含义 -> 状态表⽰；
b.
函数体 -> 状态转移⽅程；
c.
递归出⼝ -> 初始化。
解法一：记忆化搜索
解法二：动态规划
例题四
解法（暴搜 -> 记忆化搜索）：
算法思路：
暴搜：
a.
递归含义：给 dfs ⼀个使命，给他⼀个区间
[left, right]
，返回在这个区间上能完胜的最⼩费⽤；
b.
函数体：选择 [left, right] 区间上的任意⼀个数作为头结点，然后递归分析左右⼦树。
求出所有情况下的最⼩值；
c.
递归出⼝：当 left >= right 的时候，直接返回 0
。
记忆化搜索：
a.
加上⼀个备忘录；
b.
每次进⼊递归的时候，去备忘录⾥⾯看看；
c.
每次返回的时候，将结果加⼊到备忘录⾥⾯。
例题五
解法（暴搜 -> 记忆化搜索 ）：
算法思路：
暴搜：
a.
递归含义：给 dfs
⼀个使命，给他⼀个下标
[i, j]
，返回从这个位置开始的最⻓递增路径的⻓度；
b.
函数体：上下左右四个⽅向瞅⼀瞅，哪⾥能过去就过去，统计四个⽅向上的最⼤⻓度；
c.
递归出⼝：因为我们是先判断再进⼊递归，因此没有出⼝~
记忆化搜索：
a.
加上⼀个备忘录；
b.
每次进⼊递归的时候，去备忘录⾥⾯看看；
c.
每次返回的时候，将结果加⼊到备忘录⾥⾯。
