使用动态编程在给定字符串中计数组合

Question

我在“算法和数据结构” 书中找到了一个练习，我无法解决。

从字符表开始：

| left | center |
|:---- |:-------|
| A    | 0      |
| B    | 00     |
| C    | 001    |
| D    | 010    |
| E    | 0010   |
| F    | 0100   |
| G    | 0110   |
| H    | 0001   |

这意味着从给定的字符串s = 00100开始，有5可能被解码的序列：ada ，af，caa，cb或ea。

显然不是所有字符串都可以解码（例如1111）。

编写一个程序（在Java中），该程序可以计算可以通过 s 通过动态编程来编码 s 的序列数量。

另一个示例：字符串00010010001001001001001001001001100具有5567可能的序列。

提示： 子问题是 prefixes s

我的尝试：

/**
 * this is the main part of the algorithm. I feel like this is way too slow
 * and it doesn't use dynamic programming.
 * 'encodings' is just an ArrayList with the specified values (e.g 00).
 */
private void count(String str) {
  for (String c : encodings) {
    if (str.length() > c.length()) {
      String subStringCodLength = str.substring(0, c.length());
      if (subStringCodLength.equals(c)) {
        String substring = str.substring(c.length());
        count(substring);
      }
    } else if (str.length() == c.length()) {
      if (encodings.contains(str)) {
        this.numOfDecodings++;
        break;
      }
    }
  }
}

Answer 1

动态编程中有两种方法： remoization 和制表。

两者都是基于子问题的先前计算的结果的结果。正如提示所述，根据给定字符串的前缀将问题分为子问题。

Memoization

Memoization 技术与递归一起使用。存储中间结果的平均值的一个很好的选择是MAP。

实施递归时，我们需要描述两种情况：

• 基本情况 - 代表一个简单的边缘案例（或一组边缘案例）预先知道结果。对于这个问题，此类边缘案例为：

  • 给定的字符串是空的，结果将为1（一个空的二进制字符串“”结果在一个空字符串字符串“”“”中），
  • 另一种情况是无法解码给定的二进制字符串，结果将为0（在下面的解决方案中，当执行递归案例时自然而然地解决），
  • 给定字符串的结果已经计算并包含在地图中。

• 递归案例 - 解决方案的一部分，递归调用是制成的，而主要逻辑居住的时候。在递归情况下，我们需要在字符串的开头找到每个二进制“二进制字母” ，然后通过传递子字符串递归调用该方法（没有“字母” ）作为参数。这些递归调用的结果需要累积，存储在地图中，然后作为返回值提供。

它的外观是：

public static int count(String str, List<String> letters, Map<String, Integer> vocab) {
    if (str.isEmpty()) { // base case - a combination was found
        return 1;
    }
    if (vocab.containsKey(str)) { // result was already computed and present in the map 
        return vocab.get(str);
    }

    int count = 0;

    for (String letter: letters) {
        if (str.startsWith(letter)) {
            count += count(str.substring(letter.length()), letters, vocab);
        }
    }
    vocab.put(str, count); // storing the total `count` into the map

    return count;
}

制表

制表技术不是基于递归，而是利用循环。

这使得这种方法更加可靠，因为递归有一定的限制，尤其是在Java中。制表允许处理一个可以使用 Memoization 产生StackoverFlowerRor的大量输入。

通常，阵列用于在实现制表时存储中间结果。

要解决此问题，我们需要使用给定字符串 + 1的长度创建一个 array 。数组的每个元素将代表使用一组“二进制字母” 的索引0从索引0收缩的方法数量。最终结果将存储在数组的最后一个位置。

要初始化 array ，我们需要将1的值设置为对应于 “二进制字母” 的每个元素给定字符串的前缀。它是在pupulate（）方法中完成的。然后，我们需要根据已经找到的组合来迭代数组搜索可以联系的可能组合（即基于不是0的数组元素）。

public static int count(String str, List<String> letters) {
    int[] tab = new int[str.length() + 1];
    
    populate(str,  letters,  tab);
    
    for (int i = 1; i < tab.length; i++) {
        if (tab[i] == 0) continue;
        for (String letter: letters) {
            if (i + letter.length() >= tab.length) continue;
            
            if (str.substring(i, i + letter.length()).equals(letter)) {
                tab[i + letter.length()] += tab[i];
            }
        }
    }
    return tab[tab.length - 1];
}

public static void populate(String str, List<String> letters, int[] tab) {

    for (String letter: letters) {
        if (letter.length() >= tab.length) continue;
    
        if (str.startsWith(letter)) {
            tab[letter.length()] += 1;
        }
    }
}

demo

main（）

public static void main(String[] args) {
    
    List<String> letters = List.of("0", "00", "001", "010", "0010", "0100", "0110", "0001"); // binary letters

    System.out.println(count("000100100010010000100100001001100", letters, new HashMap<>())); // Memoization
    System.out.println(count("000100100010010000100100001001100", letters)); // Tabulation
}

输出：

5567   // Memoization
5567   // Tabulation

a链接到在线演示