现有一串神秘的密文 ciphertext，经调查，密文的特点和规则如下：

密文由非负整数组成

数字 0-25 分别对应字母 a-z

请根据上述规则将密文 ciphertext 解密为字母，并返回共有多少种解密结果。

示例 1：

**输入：**ciphertext = 216612
**输出：**6
**解释：**216612 解密后有 6 种不同的形式，分别是 “cbggbc”，“vggbc”，“vggm”，“cbggm”，“cqgbc” 和 “cqgm”

提示：

0 <= ciphertext < 2^(31)

当你面对 216612 时，会发现：

想要知道整个序列有多少种解法，取决于你如何处理最后一位（或两位）数字。

如果你把最后的 2 单独解密，那么剩下的问题就是 21661 的解法数。

如果你把最后的 12 合并解密，那么剩下的问题就是 2166 的解法数。

很容易想到动态规划，用dp[i]表示前i位的解密结果

有dp[i] = dp[i-1] + dp[i-2]，（i与i-1位在10-26之间时加dp[i-2]）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
int crackNumber(int ciphertext) {
string str = to_string(ciphertext);
int len = str.size();
if (len == 0 || len == 1)
return len;
vector<int> dp(len + 1);
// dp[x] = dp[x-1]+dp[x-2](10-26之间时才加)
dp[0] = 1;
int mid = stoi(str.substr(0, 2));
if (mid < 26 && mid >= 10) {
dp[1] = 2;
} else {
dp[1] = 1;
}
for (int i = 2; i < len; i++) {
int mid = stoi(str.substr(i - 1, 2));
if (mid < 26 && mid >= 10) {
dp[i] = dp[i - 1] + dp[i - 2];
} else {
dp[i] = dp[i - 1];
}
}

return dp[len - 1];
}
};