c++ - 查找给定数量的可能解码数量(动态编程)

我正在尝试解决每个字母都有各自数字的问题，例如a-1，b-2 .... z-26。
现在给定一个数字，它可以通过多种方式解码该问题。考虑一个可以将25114解码为“BEAN”，“BEAAD”，“YAAD”，“YAN”，“YKD”和“BEKD”的示例。这可以用6种方式解码。
我已经用C++编写了代码，但是得到了错误的答案。请更正我的代码。

#include<bits/stdc++.h>
using namespace std;
int total = 0;
int arr[100001];
void func(int start,int end,int factor){
    if(start==end)
        return;
    int j =start;
    if(factor==2&&j==end-1)//if j is the last element and factor is 2,accessing j+1 element is illegual
        return;
    if(factor==2){
        if((arr[j]*10+arr[j+1])>26)
            return;
        else{
            total++;
            func(start+2,end,1);
            func(start+2,end,2);
        }
    }
    else{//factor is 1
    total++;
    func(start+1,end,1);
    func(start+1,end,2);
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int p;
        cin>>p;
        arr[i]=p;
    }
    func(0,n,1);
    func(0,n,2);
    cout<<total<<endl;
    return 0;
}

本质上，我的代码正在做的是固定给定数组中的一个数字(使用给定数组中的一位或两位数字)并递归直到所有组合都被覆盖。例如，考虑到上述情况，我首先选择“2”作为我的第一位数字，并将其解码为“B”(因数= 1)，然后选择“25”并将其解码为“E”(因数= 2)。
**以下是以下代码的输入和输出
输入:25114
预期产量:6
我的输出:15
输入:3333333333(10位数)
预期输出:1
我的输出:10

最佳答案

基于问题的原始程序，我建议仅在到达末尾时计算编码(if(start==end))。

由于func将始终被factor=1和factor=2调用两次，因此我可以自由选择任一个计数条件。

这是修改后的代码:

#include<bits/stdc++.h>

using namespace std;
int total = 0;
int arr[100001];
void func(int start,int end,int factor){
    if(start==end) {
        if(factor == 1) total++; // count once when reaching the end
        return;
    }
    int j =start;
    if((factor==2) && (j==end-1))//if j is the last element and factor is 2,accessing j+1 element is illegal
        return;
    if(factor==2){
        if((arr[j]*10+arr[j+1])>26)
            return;
        else{
            //total++;
            func(start+2,end,1);
            func(start+2,end,2);
        }
    }
    else{//factor is 1
        //total++;
        func(start+1,end,1);
        func(start+1,end,2);
    }
    return;
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int p;
        cin>>p;
        arr[i]=p;
    }
    func(0,n,1);
    func(0,n,2);
    cout<<total<<endl;
    return 0;
}

这将从问题中的示例输入中计算出预期结果。

$ echo 5 2 5 1 1 4|./program
6
$ echo 10 3 3 3 3 3 3 3 3 3 3|./program
1

有改进的空间。

我无需修改全局变量，而是从func返回组合的数量，并将值添加到更高级别。

我还将处理在称为 func的中而不是在调用方中的2位数字和1位数字之间的区别。

像这样的伪代码:

int func(int start, int end)
{
    if(remaining length is <2) {
        // we reached the end, so this is one combination
        return 1;
    }
    if(two-digit number is >26) {
        // only a 1-digit number is possible, count remaining combinations
        return func(start+1, end);
    }
    // both a 1-digit or 2-digit number is possible, add the remaining combinations for both cases
    return func(start+1) + func(start+2);
}

关于c++ - 查找给定数量的可能解码数量(动态编程)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/60969309/