找出给定数目的可能解码数目（动态编程）

Question

我正在尝试解决每个字母都有各自数字的问题，例如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

我正在尝试解决每个字母都有各自数字的问题，例如a-1，b-2 .... z-26。现在给出一个数字，这个问题可以通过几种方式解码。考虑一个例子...

Answer 1

您的问题被标记为“动态编程”，但仅此而已。相反，请考虑状态空间及其边界条件：