题目：
将给定的数转换为字符串，原则如下：1对应 a，2对应b，…..26对应z，例如12258可以转换为”abbeh”, “aveh”, “abyh”, “lbeh” and “lyh”，个数为5，编写一个函数，给出可以转换的不同字符串的个数。
这是第二课第三题
两种解法：暴力递归和动态规划
#include<iostream>
#include<string>
#include<vector>
using namespace std;
//产生一个10000-100000的随机数
int CreatRandomNum(){
/*
要取得[a,b)的随机整数，使用(rand() % (b-a))+ a;
要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a;
要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1;
*/
return (rand()%90000)+10000;
}
//暴力递归
int Process(string input, int index){
//只有空串时会遇到这种情况，所以返回唯一的一种情况，空串
if(index==input.length()) return 1;
//如果当前位置的值为0，则没办法转成任何字母
if(input[index]=='0') return 0;
//此时该位置不为0 ，则肯定有结果。res的值为当前的解以及第index+1到最后的那一段字符串的结果的和
int res=Process(input, index+1);
//此时遇到了字符串的结尾，无法再继续往下递归了，因此染回结果res
if(index==input.length()-1) return res;
//如果当前位置和其后面的位置的数字组合不大于26，说明两个数可以组合出一种情况
//此时res要加上index+2到结尾的情况
if(((input[index]-'0')*10+input[index+1]-'0')<27)
res+=Process(input, index+2);
return res;
}
//动态规划
int dp(string input){
//初始长度为input.length()+1，因为有可能会有空串的情况
//应该把该结果放在动态规划数组索引位置为input.length()的位置，因此初始化长度为input.length()+1
vector<int>con(input.length()+1);
//把空串的情况存放在空串会发何时能的对应位置上
//空串的时候，只有一种结果，所以此时的值为1
con[input.length()]=1;
//最后一位如果是0，则此处无解，否则此处是一种字母，结果为1
con[input.length()-1]=input[input.length()-1]=='0'?0:1;
for(int i=input.length()-2; i>=0; i--){
if(input[i]=='0') con[i]=0;
else
con[i]=con[i+1]+
(((input[i]-'0')*10+(input[i+1]-'0'))<27?con[i+2]:0);
}
return con[0];
}
int main(){
//把数字转成字符串
string input=to_string (CreatRandomNum());
//暴力递归
//cout<<Process(input, 0)<<endl;
//动态规划
//cout<<dp(input)<<endl;
cout<<input<<endl;
Process(input, 0)==dp(input)?cout<<"good"<<endl:cout<<"fucking !!! fuck!!!"<<endl;
return 0;
}
虽然做出来了，但是感觉有点夹生。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/101277.html原文链接：https://javaforall.net
