leetcode165.解密数字

题目表述：

这道题目和斐波那契数列以及跳台阶问题十分相似。

斐波那契数列：0、1、1、2、3、5, 8、13、21、34 …… 

leetcode跳台阶问题：1、1、2、3、5, 8、13、21、34.......

这类题目的特点都是第N项的结果等于前两项的和。

但是解密数字不一样，前面几道题目都是无条件的，直接把前两项的和相加就可以了，这个题目不能直接相加，而是需要判断，然后再进行运算。

假设f(i)代表i个数字之前的解，那么新加入一个数字后，需要考虑两种情况，第一种情况这个数字只能单独翻译成一个字母，这种情况下加了也白加，f(i+1) = f(i); 第二种情况就是这个数字还能和第i个数字联合起来翻译成一个字母，比如10～25之间的两位数都可以被翻译成字母。那这种情况下f(i) = f(i-1) + f(i-2)。事实上因为这个地方无论是个位数还是两位数，最多只能翻译成1种字母，如果可以翻译成多种字母，那么就成了f(i) = g(i) * f(i-1) + g(i-1, i) * f(i-2)。

所以有公式f(i) = f(i-1) +f(i-2) 或者 f(i) = f(i-1)。按道理来说，i是大于等于2的，但是这里有个问题

f(0)=1,这是必然的，但是f(1)是1还是2就难说了。所以还要计算f(1) = f(0) + f(-1)

在斐波那契数列和登台阶的问题中，f(-1)都被设定成了0，但是这里设定成0显然是不合适的。按照f(1)的取值和计算公式应该设定成1

代码：

class Solution {
public:int crackNumber(int ciphertext) {if(ciphertext<10)return 1;string src = to_string(ciphertext);// f(i) = g(i) * f(i-1) + g(i-2) * f(i-2)// f(i) = f(i-1) + f(i-2), i>=2// f(2) = f(1) + f(0)// f(1) = f(0) + f(-1)//   ?  =  1 + ?//.  r = q + pint r, p, q;r = 0;p = 1;q = 1;for(int i=1; i<src.size(); ++i){auto pre = src.substr(i-1, 2);if(pre>="10" && pre<="25"){r = p+q;}else{r = q;}p = q;q = r;} return r;}};

这是一条吃饭博客，由挨踢零声赞助。学C/C++就找挨踢零声，加入挨踢零声，面试不挨踢！