zs-t18--数字字符转化字符串个数--dp
作者:
orange0912
,
2021-12-07 10:24:21
,
所有人可见
,
阅读 237
//规定1和A对应、2和B对应、3和C对应...26和Z对应
//那么一个数字字符串比如"111”就可以转化为:
//"AAA"、"KA"和"AK"
//给定一个只有数字字符组成的字符串str,返回有多少种转化结果
#include <iostream>
using namespace std;
const int N=100001;
int n;
string str;
//递归思路
int dfs(int u) //s1[0...u]已经转化,当前从u开始尝试转化的方法数
{
if(u==n) return 1;//越界的时候 找到一种可行方案
if(str[u]=='0') //0不能单独称为转化的字符
return 0;
//str[u]介于1--9之间
int ways=dfs(u+1); //单独转化str[u]的方案数
// u和 u+1组合在一起可以转化的方案数
if(u+1<n&&( str[u] -'0')*10+( str[u+1] -'0') <=26 )
ways+=dfs(u+2);
return ways;
}
//上述dfs过程u状态依赖于u+1和u+2 从右向左模型
int f[N];//f[i]表示 str[ i....最后字符]的转化方案数
int dp( )
{
f[n]=1; //对应上面的u==n
for(int i=n-1;i>=0;i--)//从下向上递推
{
f[i]=0;
if(str[i]!='0')
{
//单独考虑i
f[i]=f[i+1];
// i和 i+1组合在一起可以转化的方案数
if(i+1<n&&
( str[i] -'0')*10+( str[i+1] -'0') <=26 )
f[i]+=f[i+2];
}
}
return f[0];
}
int main()
{
cin>>str;
n=str.size();
cout<<dp();
return 0;
}