1.2

记忆化搜索Memoization是一种优化搜索算法的技术主要用于减少重复计算提高算法效率。

它通过存储已经计算过的结果来避免对同一问题的重复计算特别适用于‌递归算法中存在大量完全重复的递归的情况。

举个例子当我们使用普通的暴搜递归法求斐波那契数时意味着每个节点都需要遍历一遍时间复杂度为O(2^N)但是这其中出现大量完全重复的递归树大量重复的递归导致时间效率严重降低。

这时我们就可以使用一个“备忘录”所出现过的数据存起来递归时若遇见重复的问题时直接从“备忘录”中取值即可不必再次重复递归。

这样一来我们可将时间复杂优化为线性级别O(N)。

我们以添加“备忘录”的形式将数据记忆起来减少大量重复的递归这样的暴搜优化(

O(2^N)

并非所有的递归暴搜都可改为记忆化搜索只有在递归的过程中出现了大量完全相同的问题时并非相同子问题才可以使用记忆化搜索进行优化。

1.2

可变参数返回值每次进入递归的时候瞅一瞅备忘录里面是否已存在想要的结果每次递归返回的时候将结果放到备忘录中存起来

1.3

记忆化搜索是以递归的形式进行的动态规划是以递推(循环)的形式进行的记忆化搜索是自顶向下dfs(n)

dfs(n-1)

相信对于斐波那契数的计算大家都已了然于心这里就不多废话了只向大家展示三中不同解法

动态规划解法(暴搜优化)O(N)

经过分析可以发现到达(x,y)位置的路径数到达(x,y-1)的路径数到达(x-1,y)的路径数

设计递归函数体dfs(m,n)

经过验证纯暴搜解法是会超时的经分析问题中出现了大量重复的问题采取记忆化搜索算法和动态规划进行优化。

2.2.2

函数头dfs(pos)//pos位置处的最长子序列从当前位置pos开始选出后面位置中最长的子序列len(注意要求nums[i]

nums[pos])再得len1(当加上前位置)就是当前位置的最长子序列。

2.3.2

每一种情况都需要选出左右子树中话费金额的最大值(保证能赢)每种情况话费的金额为max(左右)本身选出所有情况中花费最小的最佳策略。

2.4.2