將基本的遞歸算法轉換爲動態的自下而上列表算法

Question

問題陳述： 給定一個數字序列，計算給定數字序列的可能解碼。

實例：

12給出2：

'AB' 和 'L'

和

123給出3：

'ABC'，'LC'和'AW'

這裏是我的嘗試：

import java.util.*; 

public class decodingcount { 

static int calls = 0;  
static Map<Integer, String> codes = new HashMap<Integer, String>(); 

private static void construct(){ 
codes.put(1, "A"); 
codes.put(2, "B"); 
codes.put(3, "C"); 
codes.put(4, "D"); 
//..so on 
} 

private static int decode(String str, String built){ 

    construct();   

    int n = str.length(); 
    int count = 0; 

    if (n == 0) { 
     System.out.println(built); 
     return 1; 
    } 

     // If you have 0's, then they don't have a corresponding singular letter. Break off the recursion. 
     if (str.substring(0, 1).equals("0")) 
      return 0; 

     String x = codes.get(Integer.parseInt(str.substring(0, 1))); 

     if (x == null) 
      return 0; 

     count = decode(str.substring(1), built+x); 

     if (n > 1) { 

      // If it's more than 26, it doesn't have a corresponding letter. Break off the recursion. 
      if (Integer.parseInt(str.substring(0, 2)) > 26) 
       return 0; 

      String y = codes.get(Integer.parseInt(str.substring(0, 2))); 

      count += decode(str.substring(2), built+y); 
     } 

     return count; 
    } 

    public static void main(String[] args) { 
    System.out.println(decode(args[0], "")); 
     } 
    } 

這個運行在指數時間。我真的很努力將其轉換爲動態編程自下而上的製表算法。 Here is my attempt 。它返回0.將感謝任何幫助。

Answer 1

工作代碼：

private static int decode(String str) { 

    construct(); 

    int n = str.length(); 
    int[] count = new int[n]; 

    count[0] = 1; 

    for (int i = 1; i < n; i++) { 
     String x = codes.get(Integer.parseInt(str.substring(i, i + 1))); 
     if (str.charAt(i) != '0') 
      count[i] = count[i - 1]; 
     if (Integer.parseInt(str.substring(i - 1, i + 1)) <= 26 && str.charAt(i - 1) != '0') 
      count[i] += (i - 2 >= 0 ? count[i - 2] : 1); 
    } 

    return count[n - 1]; 

}