59. 把数字翻译成字符串
题目描述
给定一个数字,我们按照如下规则把它翻译为字符串:
0 翻译成 a,1 翻译成 b,……,11 翻译成 l,……,25 翻译成 z。
一个数字可能有多个翻译。
例如 12258 有 5 种不同的翻译,它们分别是 bccfi、bwfi、bczi、mcfi 和 mzi。
请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。
数据范围
输入数字位数 [1,101]。
样例
输入:"12258"
输出:5
算法1 dp
算法流程
状态表示:f[i] — 前i位数字的不同表示方式个数
状态计算:i单独翻译+i和i-1一起翻译
f[i] = f[i - 1] + f[i - 2]
边界:f[0] = 1
C++ 代码
class Solution {
public:
int getTranslationCount(string s) {
int n = s.size();
vector<int> f(n + 1);
f[0] = 1; //字符串为空时,存在空这种方案
for(int i = 1; i <= n; i++)
{
f[i] = f[i - 1]; //i自己翻译
if(i > 1) //i-1和i共同翻译出一个字母
{
int t = s[i - 1] - '0' + (s[i - 2] - '0') * 10;
if(t >= 10 && t <= 25) f[i] += f[i - 2];
}
}
return f[n];
}
};
总结
拿到题的时候还是能知道应该用dp来做
但是状态状态表示和状态转移不知道怎么设计
应该还是dp做的不够多