動態編程或回溯？

Question

我的朋友給我以下的問題：

Input: A matrix of letters and a word. 
Output: The frequency of the word in the matrix assuming 
    you can move left, right, up and down in the matrix to form the word. 

例如：

Input: 
S E X Y 
A S E A 
A A X A 
A A Y A 
And word is SEXY. 

Output: 
4 (four times in matrix of letters) 

這是我的代碼解決的問題：

package backtracking; 

public class CountFrequency { 
    private char[][] matrixOfLetter; 
    private String word; 
    private int n, m; 
    private int lengthOfWord; 
    private int[][] matrixCountFrequency; 

    public CountFrequency(int n, int m, String word) { 
     matrixOfLetter = new char[n][m]; 
     this.word = word; 
     this.n = n; 
     this.m = m; 
     this.lengthOfWord = word.length(); 

     matrixCountFrequency = new int[n][m]; 
     for (int i = 0; i < n; ++i) 
      for (int j = 0; j < n; ++j) 
       matrixCountFrequency[i][j] = 0; 
    } 

    public static void main(String[] args) { 
     CountFrequency countFrequency = new CountFrequency(4, 4, "SEXY"); 

     countFrequency.addMatrixOfLetter(0, 0, 'S'); 
     countFrequency.addMatrixOfLetter(0, 1, 'E'); 
     countFrequency.addMatrixOfLetter(0, 2, 'X'); 
     countFrequency.addMatrixOfLetter(0, 3, 'Y'); 
     countFrequency.addMatrixOfLetter(1, 0, 'A'); 
     countFrequency.addMatrixOfLetter(1, 1, 'S'); 
     countFrequency.addMatrixOfLetter(1, 2, 'E'); 
     countFrequency.addMatrixOfLetter(1, 3, 'A'); 
     countFrequency.addMatrixOfLetter(2, 0, 'A'); 
     countFrequency.addMatrixOfLetter(2, 1, 'A'); 
     countFrequency.addMatrixOfLetter(2, 2, 'X'); 
     countFrequency.addMatrixOfLetter(2, 3, 'A'); 
     countFrequency.addMatrixOfLetter(3, 0, 'A'); 
     countFrequency.addMatrixOfLetter(3, 1, 'A'); 
     countFrequency.addMatrixOfLetter(3, 2, 'Y'); 
     countFrequency.addMatrixOfLetter(3, 3, 'A'); 

     countFrequency.process(); 
     countFrequency.printResult(); 
    } 

    public void addMatrixOfLetter(int i, int j, char c) { 
     matrixOfLetter[i][j] = c; 
    } 

    public void process() { 
     for (int i = 0; i < n; ++i) 
      for (int j = 0; j < m; ++j) { 
       if (word.indexOf(matrixOfLetter[i][j]) == -1) { 
        matrixCountFrequency[i][j] = -1; 
        continue; 
       } 
       if (matrixOfLetter[i][j] == word.charAt(lengthOfWord - 1)) 
        processWithLastChar(lengthOfWord - 1, i, j); 
      } 
    } 

    public void processWithLastChar(int indexOfWord, int row, int col) { 
     matrixCountFrequency[row][col] += 1; 
     if (indexOfWord == 0) 
      return; 
     else { 
      if (row - 1 >= 0) { 
       if (matrixOfLetter[row - 1][col] == word 
         .charAt(indexOfWord - 1)) 
        processWithLastChar(indexOfWord - 1, row - 1, col); 
      } 

      if (row + 1 < lengthOfWord) { 
       if (matrixOfLetter[row + 1][col] == word 
         .charAt(indexOfWord - 1)) 
        processWithLastChar(indexOfWord - 1, row + 1, col); 
      } 

      if (col - 1 >= 0) { 
       if (matrixOfLetter[row][col - 1] == word 
         .charAt(indexOfWord - 1)) 
        processWithLastChar(indexOfWord - 1, row, col - 1); 
      } 

      if (col + 1 < lengthOfWord) { 
       if (matrixOfLetter[row][col + 1] == word 
         .charAt(indexOfWord - 1)) 
        processWithLastChar(indexOfWord - 1, row, col + 1); 
      } 
     } 
    } 

    public void printResult() { 
     int count = 0; 
     for (int i = 0; i < n; ++i) 
      for (int j = 0; j < m; ++j) { 
       if (word.charAt(0) == matrixOfLetter[i][j]) 
        count += matrixCountFrequency[i][j]; 
      } 

     System.out.println("Frequency is : " + count); 
    } 
} 

我用了一個回溯算法，但只有我當我看到最後一個單詞的時候回到原點，當看到最右側的那個單詞時，再次回到原點。

我使用計數矩陣計數字母的頻率。

動態規劃算法能解決這個問題嗎？

或者有什麼更好的想法？

Answer 1

它可以用動態規劃解決，我認爲這是最容易理解的解決方案。

爲您創建一個平行的三維矩陣。如果字母矩陣的尺寸爲n x m，並且您搜索的詞是L，則您創建矩陣dp[n][m][L]。在dp[i][j][k]中，您存儲了多少種方法可以將字母initial[i][j]用作k字母。

您有dp[i][j][k] = sum(dp[i+delta1][j + delta2][k + 1])，其中{delta1, delta2} in {{0, 1},{0, -1}, {1, 0}, {-1, 0}}。遞歸的底部是delta[i][j][L - 1] = (initial[i][j] == word[L - 1])。

如果對所有可能的i和j總結dp[i][j][l - 1]，則會給出最終結果。

希望這可以幫助你。

編輯

我必須承認，我確實在我的初步解決方案一個愚蠢的建議。我提出的動態解決方案沒有考慮到我使用過哪些字母。因此，對於矩陣

XXXX 
XABX 
XXXX 

和字符串ABAB我的算法會返回一個計數 - 將B，然後回到A和從A開始回B.這可能是錯誤的，你需要什麼。

遺憾地跟蹤您已經訪問過的內容在動態方法中並不簡單，現在我開始認爲回溯更適合您的問題。

順便說一下，在您的解決方案中，您也不會考慮這一點，但跟蹤您在回溯過程中所訪問的內容要容易得多。我也認爲回溯會更高效的記憶和性能。