将基本的递归算法转换为动态的自下而上制表算法

Question

问题陈述：给定一个数字序列，计算给定数字序列的可能解码。

示例：

12 gives 2 for:

'AB' and 'L'

和

123 gives 3 for:

'ABC', 'LC' and '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 .它 returns 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];

}

将基本的递归算法转换为动态的自下而上制表算法

Converting a rudimentary recursive algorithm to a dynamic bottom-up tabulation algorithm

java

algorithm

recursion

dynamic-programming