algorithm - 动态规划的数据结构选择

Question

为了实现一个DP算法来检测一个词是否可以分解为长度为'n'到1的子词，应该选择什么样的数据结构来缓存DP结果。示例: 单词“pita”可以分解为“pit”、“it”和“i”，这些都是有效的字典单词。DP算法应该检测到这样的词。

我可以想象我需要从长度为 1 的单词开始并构建长度递增的子字符串，但我无法获得可以有效存储子问题结果的数据结构

Answer 1

如果您按顺序处理单词，则不需要跟踪前一个单词，因为您不会再次访问它们，但是您可以使用缓存来缓存字典中先前查找的子单词。如果我理解这个问题，那么我认为以下 Java 代码可能会对您有所帮助:

String term = "pita";
Set<String> dictionary = new HashSet<String>();
boolean ans = true;
for(int i = 0; i < term.length() && ans == true; i++) {
    for(int j = i + 1; j < term.length(); j++) {
        String subTerm = term.substring(i, j);
        if(!dictionary.contains(subTerm)){
            ans = false;
            break;
        }
    }
}
System.out.println("ans [" = ans + "]");

对于字典，您可以使用哈希表，它支持采用 O(1) 来检查子词存在与否。如果您缓存以前检查过的子词，它将采用相同的 O(1)

我认为这个问题适用于排序和搜索技术而不适用于 DP，因为它没有使用以前的答案来生成当前答案。