动态编程--记忆化

Question

我正在处理一个DP问题，在这个问题中，一个删除了空格的单词串，我需要同时实现buttom-up和memoization版本，以将字符串分割为单独的英语单词。然而，我得到了向上的版本，然而，memoization似乎有点复杂。

 /* Split a string into individual english words
 * @String str the str to be splitted
 * @Return a sequence of words separated by space if successful,
     null otherwise
 */
public static String buttom_up_split(String str){
    int len = str.length();
    int[] S = new int[len+1];
    /*Stores all the valid strings*/
    String[] result = new String[len+1];  
    /*Initialize the array*/
    for(int i=0; i <= len; i++){
        S[i] = -1;
    }
    S[0] =0;
    for(int i=0; i < len; i++){
        if(S[i] != -1){
            for(int j= i+1; j <= len; j++){
                String sub = str.substring(i, j);
                int k = j;      
                if(isValidEnglishWord(sub)){
                    S[k] = 1; //set true indicates a valid split
                    /*Add space between words*/
                    if(result[i] != null){ 
                        /*Add the substring to the existing words*/
                        result[i+ sub.length()] = result[i] + " " + sub;
                    }
                    else{
                        /*The first word*/
                        result[i+ sub.length()] = sub;
                    }
                }

            }
        }
    }
    return result[len];  //return the last element of the array
}

我真的搞不懂如何将这个buttom_up_version转换成memoized版本，希望有人能帮助我。

Answer 1

好吧，我不是一个出口的记忆，但想法是有一个“记忆”以前的好英语单词。这样做的目的是节省计算时间:在本例中，是调用isValidEnglishWord()。

因此，你需要这样调整你的alorythm：

1. 遍历'str‘字符串

a substring from it

2. 检查该子字符串是否为记忆中的有效单词。
   1. It in in memory:在结果中添加一个空格和单词。
   2. It in not in memory:调用isValidEnglishWord并处理它的return.

​

它将给出类似于(未测试或编译)的内容

// This is our memory
import java.util.*

private static Map<String, Boolean> memory = new HashMap<String, Boolean>()

public static String buttom_up_split(String str){
   int len = str.length();
   int[] S = new int[len+1];

   String[] result = new String[len+1];  
   for(int i=0; i <= len; i++){
      S[i] = -1;
   }
   S[0] =0;
   for(int i=0; i < len; i++){
      if(S[i] != -1){
         for(int j= i+1; j <= len; j++){
            String sub = str.substring(i, j);
            int k = j;    

            // Order is significant: first look into memory !
            Boolean isInMemory = memory.contains(sub);
            if (isInMemory || isValidEnglishWord(sub)){
                S[k] = 1;
                if(result[i] != null){ 

                    // Memoize the result if needed.
                    if (!isInMemory) {
                        memory.put(sub, true);
                    }

                    result[i+ sub.length()] = result[i] + " " + sub;
                } else {
                    result[i+ sub.length()] = sub;
                }
            }

        }
    }
}
return result[len];

}

Answer 2

就我个人而言，我总是喜欢在不修改算法的情况下尽可能透明地使用memoization。这是因为我希望能够从memoization中单独测试算法。另外，我正在开发一个memoization库，您只需将@Memoize添加到适用于memoization的方法中即可。但不幸的是，这对你来说太晚了。

上一次我使用memoization (没有我的库)时，我使用proxy class实现了它。重要的一点是，此实现不支持递归。但这应该不是问题，因为你的算法不是递归的。

其他一些参考资料包括：

• wikipedia
• Java implementation
• memoize using proxy class

关于您的算法的备注:您如何处理包含其他单词的单词？就像“详细”包含“动词”，“理论”包含"the“等...