动态编程 - 记忆

我正在处理DP问题，其中删除空格的字符串，我需要实现buttom-up和memoization版本将字符串拆分为单个英文单词。但是，我得到了buttom-up版本，但是，记忆似乎有点复杂。动态编程 - 记忆

/* 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版本，希望有人能帮助..

来源

2012-06-02 jctank

嘛，我不是记忆化的出口，但这个想法是有“记忆“以前的英文单词很好。目标是节省计算时间：在您的情况下，调用isValidEnglishWord（）。

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

穿行“STR”字符串
从中提取
一个子checkif的子是在你的记忆的有效字。
1. 它在内存中：为结果添加空格和单词。
2. 它不在内存中：调用isValidEnglishWord并处理它的返回。

这将给像（未测试也不编译）

// 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];

}

来源

2012-06-02 07:54:11 Feugy

我个人总是倾向于尽可能透明地使用记忆化，而无需修改算法。这是因为我希望能够从记忆中分别测试算法。另外我正在研究一个memoization库，其中只需将@Memoize添加到适用于memoization的方法。但不幸的是，这对你来说太迟了。

上次我使用memoization（没有我的库）我使用proxy class实现它。一个重要的评论是这个实现不支持递归。但是这不应该成为一个问题，因为你的算法不是递归的。

一些其他的引用：

备注关于你的算法：你是如何处理那些在他们的其他单词？像“verbose”包含“动词”，“理论”包含“the”等...

来源

2012-06-03 10:45:21 misl

动态编程 - 记忆

回答

相关问题