java - 使用动态编程计算给定字符串中的组合

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。

Obviously not all strings can be decoded (e.g. 1111).

编写一个程序(Java)，通过动态编程计算可以编码S的序列数。

另一个例子:字符串000100100010010000100100001001100有5567个可能的序列。

Hint: the subproblems are the prefixes of 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

动态编程有两种方法:记忆化 和制表。

两者都基于并存储和重用先前计算的子问题结果。正如提示所示，根据给定字符串的前缀将问题划分为子问题。

内存

记忆化技术与递归一起使用。 Map 是存储中间结果的一个不错的选择。

在实现递归时，我们需要描述两种情况:

• 基本情况 - 表示一个简单的边缘情况(或一组边缘情况)，其结果是预先已知的。对于这个问题，这样的边缘情况是:

  • 给定的字符串为空，结果为 1(空的二进制字符串 "" 结果为空字母字符串 "" )，
  • 另一种情况是无法解码给定的二进制字符串，结果将为 0(在下面的解决方案中，当执行递归情况时，它会自然解析)，
  • 给定字符串的结果已计算并包含在 map 中。

• 递归情况 - 解决方案的一部分，其中递归调用以及主逻辑所在的位置。在递归情况中，我们需要找到字符串开头的每个二进制“二进制字母”，然后通过传递子字符串(不带>"letter") 作为参数。这些递归调用的结果需要累积、存储在映射中，然后作为返回值提供。

它可能看起来像这样:

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 中。制表允许处理大量输入，这些输入可能会通过记忆化产生StackOverflowError。

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

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

要初始化数组，我们需要为数组中对应“二进制字母”的每个元素设置值1，其中恰好是给定字符串的前缀。它是在 populate() 方法中完成的。然后我们需要根据已经找到的组合(即根据非 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;
        }
    }
}

演示

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 link to Online Demo