刷题 编写一个函数，给出可以转换的不同字符串的个数。 …

题目：

将给定的数转换为字符串，原则如下：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;
}

虽然做出来了，但是感觉有点夹生。