记忆性搜索

算法思路：

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(解大小).

例子：

LeetCode 140 Word Break II
这是单边catalan

def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
	word_set = set(wordDict)
	res = []
	cache = {}
	res = self.dfs(s, word_set, cache) #cat
	return res
# dfs(s) = word + dfs(s[i+1:])
def dfs(self, s, word_set, cache):
	if s == "":
		return [""]
	if s in cache:
		return cache[s]
	res = []
	for i in range(len(s)):
		if s[:i + 1] not in word_set:
			continue
		cur_list = self.dfs(s[i + 1:], word_set, cache) # i = 2, dfs("")
		for _s in cur_list: # [""]
			res.append((s[:i + 1] + " " + _s).strip()) #cat
	cache[s] = res
	return res

注意事项：

1. 终止条件返回[‘’]而不是[]，正如L017，空字符串作为初始结果。返回到上层要strip(), 因为ss可能为空
2. 子问题用f=word + f并不是f=f + word, 这样最后结果避免反转。
3. s[:i + 1]判断是否在字典中，而不是s[:i]，单词包括整个字符串。