时间戳

首页 > 解决方案 > 查找给定数字的可能解码次数（动态编程）

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

标签： c++encryptionpermutationdynamic-programming

解决方案

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

由于func总是用factor=1and调用两次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);
}

推荐阅读