动态规划学习——数字转为字母

本文介绍: 假设1对应A,2对应B,3对应C…26对应Z现在给定一个数字串，求其可以转化为多少种字母串如111可以转化为AAA,AK,KA

问题：

假设1对应A,2对应B,3对应C…26对应Z
现在给定一个数字串，求其可以转化为多少种字母串
如111可以转化为AAA,AK,KA

问题分析：

由于一共有26个英文字母，所以既可以一个数字对应一个字母，也可以两个数字对应一个字母。如11可以对应AA，也可以对应K。

所以对于每个数字都有两种情况，一是单独匹配一个字母，二是跟它后面的数字一起匹配一个字母。而只有数字小于等于26时，才能匹配到字母，所以还需添加一个判断条件。

另外，若当前数字为0，则不能匹配到字母，只有其与前面的数字组合时才有可能匹配到字母。

#include<iostream>
using namespace std;

char num[100000];
int len;
int ways2_temp[10000];

//法一：直接递归
int ways1(int index)
{
    //如果到了数组的结尾，意味着匹配成功，返回1表示成功
    if(index==len) return 1;
    //如果目前数字串以0开头，则其没有匹配的字母，返回0表示失败
    if(num[index]=='0') return 0;
    //若目前数字串不以0开头，则有两种匹配情况
    //第一种情况：让目前第一个数字匹配字母
    int t=ways1(index+1);
    //第二种情况：让目前前两个数字匹配字母，但是只有这个两位数小于等于26时才能匹配到字母
    if(index+1<len&&((num[index]-'0')*10+num[index+1]-'0')<=26){ //这里要注意需要减去'0'，因为因按照字符输入的，而不是数字
        t+=ways1(index+2);//若可以匹配，则总结果要加上第二种情况
    }
    return t;
}

//法二：动态规划，将递归转化为数组即可
int ways2()
{
    ways2_temp[len]=1;//递归的出口，也是动态规划的起点
    int i;
    for(i=len-1;i>=0;i--){
        if(num[i]=='0') ways2_temp[i]=0;
        else{
            ways2_temp[i]=ways2_temp[i+1];
            if(i+1<len&&((num[i]-'0')*10+num[i+1]-'0')<=26) ways2_temp[i]+=ways2_temp[i+2];
        }
    }
    return ways2_temp[0];
}

int main()
{
    int choice=0;
    //输入1则循环
    do{
        cout<<"请输入数组的长度"<<endl;
        cin>>len;
        int i;
        cout<<"请输入具体的数字"<<endl;
        for(i=0;i<len;i++) cin>>num[i];
        int result1=ways1(0);
        cout<<"法一 直接递归的结果为 "<<result1<<endl;
        int result2=ways2();
        cout<<"法二 动态规划的结果为 "<<result2<<endl;

        cout<<"继续请输入1"<<endl;
        cin>>choice;
    }while(choice==1);

    return 0;
}

int ways2()
{
    ways2_temp[len]=1;//递归的出口，也是动态规划的起点
    int i;
    for(i=len-1;i>=0;i--){
        if(num[i]=='0') ways2_temp[i]=0;
        else{
            ways2_temp[i]=ways2_temp[i+1];
            if(i+1<len&&((num[i]-'0')*10+num[i+1]-'0')<=26) ways2_temp[i]+=ways2_temp[i+2];
        }
    }
    return ways2_temp[0];
}