记忆性搜索

算法思路：

DFS将子问题的解存于结果中。cache[st] = result. st是子问题边界。

应用：

用于求所有可能性，且这些可能性有重复，记忆性搜索可以用于剪枝。

1. Leetcode 139
2. Leetcode 140

与DP的界线：

1. 状态转移特别麻烦如有循环依赖, 不是顺序性。如棋盘，上下左右四个方向如1197 Minimum Knight Moves和word ladder
2. 初始化状态不是特别容易找到

算法步骤：

1. key为子问题索引st，value为子问题的解。不含path和res因为类似于Catalan，用子问题返回结果来组成此轮结果。f(input, st, endIndex, cache) -> List
2. 紧跟终结条件，若在cache中，返回子问题的解。
3. 循环结束，将子问题的结果存于cache。

注意事项：

1. cache是一个解的集合，所以终止条件返回也需要是一个list

Python代码：

def dfs(self, input, cache) -> List[int]:
	if <终止条件>:
		return [] # remember to use list
	if input in cache:
		return cache[input]
	res = []
	for i in range(len(input)):
		anwser = self.dfs(input[:i], cache)
		res.append(anwser)
	cache[input] = res
	return res

算法分析：

时间复杂度为O(解大小)，空间复杂度O(解大小).