求给定二进制字符串的所有解码组合数量的Java实现

我们可以使用动态规划的思想来解决这个问题。我们可以用一个长度为n+1的数组dp[]来记录给定长度为n的二进制字符串的解码组合数量。我们遍历字符串中的每个字符，如果当前字符为1，则dp[i+1]=dp[i]+dp[i-1]，因为我们可以将当前字符与前一个字符组合成一个二位数来表示一个字母。如果当前字符为0，则dp[i+1]=dp[i-1]，因为0只能与前面的1组合成一个字母。如果当前字符为其他数，则dp[i+1]=dp[i]，因为这种情况下前一个字符不能组合。最后返回dp[n]即可。

以下是Java代码示例：

public static int countDecoding(String s){
    int n = s.length();
    int[] dp = new int[n+1];
    dp[0] = 1;
    dp[1] = 1;
    for(int i=1;i<n;i++){
        if(s.charAt(i) == '1'){
            dp[i+1] = dp[i] + dp[i-1];
        }else if(s.charAt(i) == '0'){
            dp[i+1] = dp[i-1];
        }else{
            dp[i+1] = dp[i];
        }
    }
    return dp[n];
}

我们可以测试一下这个函数：

public static void main(String[] args) {
    String s = "101";
    System.out.println(countDecoding(s)); // 输出2
}