java - Javaでの動的プログラミング辞書演習のボトムアップアプローチ

Question

ここに私が解決したい問題があります: 辞書、つまり m 個の文字列のセット S と別の文字列 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());
}

}

ボトムアップのアプローチを使用してこの問題を解決する方法を見つけることができないようです...誰かがボトムアップでそれを解決する方法を教えてくれたら、それは素晴らしいことです