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

本文介绍: 假设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，则不能匹配到字母，只有其与前面的数字组合时才有可能匹配到字母。

从左到右开始扫描数组，假定从下标为i开始到最后的结果数为result(i)，即不考虑i前面的数字，则result(i)=result(i+1)+result(i+2)，

代码：

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

可以看到，起始条件是ways2_temp[len]=1;

举例说明：

假设有数组[2,1,0,3,2]，数组的长度为5

num[4]:[2]

ways2_temp[5]=1

ways2_temp[4]=ways2_temp[5]=1，这用常识来看是正确的，因为只考虑num[4]以后的数即[2]，只有一种结果

num[3]:[3,2]

ways2_temp[4]=1

现在在前面加上一个数3，要判断32可以对应几种可能

又因为32>26，不能将其合并起来看，所以3和2只能单独对应一个字母，不满足代码中第二个if条件

按照代码，ways2_temp[3]=ways2_temp[4]=1，即32只对应一种可能

num[2]:[0,3,2]