1

这是我要解决的问题：给你一个字典，即一组 m 个字符串和一个单独的字符串 t。您需要输出 t 可以分解为的最小子串数，使得这些子串的并集为 t 并且所有子串都属于字典。例子：

输入：

5

0 1 11 1101 000

1111001000

输出：

6

我已经使用自上而下的记忆方法（在java中）解决了它：

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int m = sc.nextInt();
    String[] s = new String[m];
    for(int i = 0; i < m; ++i){
    s[i] = sc.next();
    }
    String t = sc.next();        
    System.out.println(topDown(m, s, t));
}

public static int topDown(int m, String[] s, String t) {
    int r[] = new int[m + 1];
    for (int i = 0; i <= m; ++i) {
        r[i] = Integer.MAX_VALUE - 3;
    }
    return memo(m, s, t, r);
}

public static int memo(int m, String[] s, String t, int[] r) {
    int best = Integer.MAX_VALUE - 3;
    for (int i = 0; i < m; ++i) {
        if (t.equals(s[i])) {
            r[m] = 1;
            return 1;
        }
    }
    if (m == 0) {
        best = 0;
    } else {
        int a;
        for (String str : s) {
            if (t.endsWith(str)) {
                a = 1 + memo(m, s, replaceLast(t, str, ""), r);
                if (best > a)
                    best = a;
            }
        }
    }
    r[m] = best;
    return best;
}

public static String replaceLast(String string, String substring,
        String replacement) {
    int index = string.lastIndexOf(substring);
    if (index == -1)
        return string;
    return string.substring(0, index) + replacement
            + string.substring(index + substring.length());
}

}

我似乎无法找到使用自下而上方法解决此问题的方法......如果有人可以告诉我如何用自下而上解决它会很棒

4

0 回答 0