将一个简单的递归算法转换为动态自下而上的表格算法

Question

将一个简单的递归算法转换为动态自下而上的表格算法

javaalgorithmrecursiondynamic-programming

3

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

例子：

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], ""));
        }
    }

这个算法运行时间是指数级别的。我很难将其转换为一种动态规划的自底向上的表格化算法。这是我的尝试，但它返回了0。如果能得到任何帮助，将不胜感激。

- Siddhartha

对于什么输入，它会返回0？ - advocateofnone

@sasha 如果我使用“1214”调用它，我会得到一个0。 - Siddhartha

@btilly 1203有1种可能的解码方式：ATD。这是完整的问题。我没有解释清楚。 - Siddhartha

你能把你的底部也放在这里吗？我无法访问链接 :) - Pham Trung

好的，我可以访问它，谢谢 :) - Pham Trung

显示剩余4条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Pham Trung · Accepted Answer

工作代码:

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];

}