определение количества возможных расшифровок заданного числа (динамическое программирование c)

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

По сути, мой код состоит в том, что он фиксирует одно число из заданного массива (используя одну ди git или две цифры из данного массива) и повторяется до тех пор, пока все комбинации покрыты. например, учитывая вышеупомянутый случай, я сначала выбираю «2» в качестве моего первого di git и декодирую его как «B» (фактор = 1), а затем выбираю «25» и декодирую его как «E» (фактор = 2) , ** ниже приведены входные и выходные данные следующего кода: 25114 ожидаемый вывод: 6 my output: 15 input: 3333333333 (10 цифр) ожидаемый вывод: 1 my output: 10

Answer 1

Исходя из исходной программы из вопроса, я предлагаю подсчитывать кодировки только при достижении конца (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 и добавил бы значения на более высоком уровне.

Я бы также обработал различие между 2-ди git и цифры 1-ди git в , называемые func вместо номера вызывающего абонента.

Примерно так: псевдокод:

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);
}

Answer 2

Ваш вопрос помечен как "dynamici c -programming", но это не что иное, как. Вместо этого, подумайте о пространстве состояний и его граничных условиях:

• Пустая строка имеет нулевое кодирование;
• Один ди git имеет одну кодировку;
• Строка n-di git имеет столько кодировок, сколько (n-1) -di git подстрока плюс столько кодирований, сколько (n-2) -di git подстрока, если первые две цифры < = 26.

Таким образом, мы можем пройти строку назад и сохранить промежуточные результаты для повторного использования:

uint64_t solve(std::vector<int>& digits) {
    const int n = digits.size();
    std::vector<int> encodings(n+1);
    encodings[n] = 1;
    for (int i = n-1; i >= 0; i--) {
        bool two_digits_fit = (i < n - 1) && (digits[i] * 10 + digits[i+1]) <= 26; // What if digits[i] == 0?
        encodings[i] = encodings[i+1] + (two_digits_fit ? encodings[i+2] : 0);
    }
    return encodings[0];
}