![[Pasted image 20241109182035.png]]

回顾回溯

构建以单词数量m的m叉树，每次构建的时候就继续分叉，直到构建能构建出一个完整的目标单词。

问题

冗余计算，如 “a”，“aa”

动规解法

不管是什么算法，消除冗余计算的方法就是加备忘录。回溯算法也可以加备忘录，我们可以称之为「剪枝」，即把冗余的子树给它剪掉。

解题核心：dpFound备忘录记录子树可不可以被切分（用hash map）