假設我們有一串二進制值，其中某些部分可能對應于特定字母，例如：
A = 0
B = 00
C = 001
D = 010
E = 0010
F = 0100
G = 0110
H = 0001
例如，如果我們假設 string "00100"，我們可以有5不同的可能性：
ADA
AF
CAA
CB
EA
我必須使用動態編程提取確切數量的組合。
但是我在子問題的制定和相應的解向量的組成方面有困難。
我很欣賞正確演算法公式的任何跡象。
class countString {
static int count(String a, String b, int m, int n) {
if ((m == 0 && n == 0) || n == 0)
return 1;
if (m == 0)
return 0;
if (a.charAt(m - 1) == b.charAt(n - 1))
return count(a, b, m - 1, n - 1)
count(a, b, m - 1, n);
else
return count(a, b, m - 1, n);
}
public static void main(String[] args) {
Locale.setDefault(Locale.US);
ArrayList<String> substrings = new ArrayList<>();
substrings.add("0");
substrings.add("00");
substrings.add("001");
substrings.add("010");
substrings.add("0010");
substrings.add("0100");
substrings.add("0110");
substrings.add("0001");
if (args.length != 1) {
System.err.println("ERROR - execute with: java countString -filename- ");
System.exit(1);
}
try {
Scanner scan = new Scanner(new File(args[0])); // not important
String S = "00100";
int count = 0;
for(int i=0; i<substrings.size(); i ){
count = count count(S,substrings.get(i),S.length(),substrings.get(i).length());
}
System.out.println(count);
} catch (FileNotFoundException e) {
System.out.println("File not found " e);
}
}
}
uj5u.com熱心網友回復：
本質上，動態編程是一種增強的蠻力方法。
就像在蠻力的情況下一樣，我們需要生成所有可能的結果。但是與普通的蠻力相反，問題應該被分成更小的子問題，并且每個子問題的先前計算的結果應該被存盤和重用。
由于您使用的是遞回，因此您需要應用所謂的記憶技術來存盤和重用中間結果。在這種情況下，HashMap將是存盤結果的完美手段。
但是在應用memoization以便更好地理解它之前，先從一個干凈且簡單且正常作業的遞回解決方案開始是有意義的，然后才使用 DP 對其進行增強。
普通遞回
每個遞回實作都應該包含兩個部分：
基本情況- 表示一個簡單的邊緣情況（或一組邊緣情況），其結果是預先知道的。對于這個問題，有兩種極端情況：給定字串的長度是
0并且結果是1（一個空的二進制字串""導致一個空的字母字串""），另一種情況是不可能解碼給定的二進制字串和結果將是0（在下面的解決方案中，它會在執行遞回案例時自然解決）。遞回案例- 解決方案的一部分，其中遞回呼叫和主邏輯駐留。在遞回的情況下，我們需要在字串的開頭找到每個二進制“二進制字母”，然后通過傳遞子字串（不帶“字母”）遞回呼叫該方法。這些遞回呼叫的結果需要累積在從方法回傳的總數中。
為了實作這個邏輯，我們只需要兩個引數：要分析的二進制字串和二進制字母串列：
public static int count(String str, List<String> letters) {
if (str.isEmpty()) { // base case - a combination was found
return 1;
}
// recursive case
int count = 0;
for (String letter: letters) {
if (str.startsWith(letter)) {
count = count(str.substring(letter.length()), letters);
}
}
return count;
}
這個簡潔的解決方案已經能夠產生正確的結果。現在，讓我們通過應用memoization將這個蠻力版本變成基于 DP 的解決方案。
動態規劃
正如我之前所說，aHashMap將是存盤中間結果的完美方法，因為它允許將計數（組合數）與特定字串相關聯，然后幾乎立即檢索該數字（在O(1)時間內）。
它可能看起來像這樣：
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;
}
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("00100", letters, new HashMap<>())); // DP
System.out.println(count("00100", letters)); // brute-force recursion
}
輸出：
5 // DP
5 // plain recursion
在線演示的鏈接
uj5u.com熱心網友回復：
希望這可以幫助。想法是使用這些值創建每個可能的字串，并檢查是否input以該值開頭。如果沒有，則切換到另一個索引。
如果您準備好測驗用例，您可以驗證更多。我只測驗了 2-3 個值。
public int getCombo(String[] array, int startingIndex, String val, String input) {
int count = 0;
for (int i = startingIndex; i < array.length; i ) {
String matchValue = val array[i];
if (matchValue.length() <= input.length()) {
// if value matches then count 1
if (matchValue.equals(input)) {
count ;
System.out.println("match Found---->" count); //ommit this sysout , its only for testing.
return count;
} else if (input.startsWith(matchValue)) { // checking whether the input is starting with the new value
// search further combos
count = getCombo(array, 0, matchValue, input);
}
}
}
return count;
}
在主要方法中
String[] arr = substrings.toArray(new String[0]);
int count = 0;
for (int i = 0; i < arr.length; i ) {
System.out.println("index----?> " i);
//adding this condition for single inputs i.e "0","010";
if(arr[i].equals(input))
count ;
else
count = count getCombo(arr, 0, arr[i], input);
}
System.out.println("Final count : " count);
我的測驗結果：
input : 00100
Final count 5
input : 000
Final count 3
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/482714.html