139.单次拆分。给定一个单词和字典，检查单词是否可以通过字典里的元素线性组合而成。看到这个问题第一反应是通过回溯法，每次对单词开头进行查找，在字典里找到的话就将当前字减去，直到单词为空。本身算法并没有太大的问题，但是提交的时候碰到一些比较极端的用例会出现超时的情况。比如单词为aaaaaaaaaaaaaaaaaaab，字典为[a, aa, aaa, aaaa, aaaaa]，此时如果进行回溯的话就会需要很大的内存空间且耗费很多时间，为了不超时，想到用空间换时间，即将前面单词匹配结果进行存储，后面的检查情况结合当前匹配结果和之前匹配结果，也即动态规划，这样就避免了出现超时的情况。
原文：https://www.cnblogs.com/junenatte/p/13808395.html