91.解码方法
该题类似于爬楼梯
方法一：动态规划
对于给定的字符串 s，设它的长度为 n，其中的字符从左到右依次为 s[1],s[2],⋯,s[n]。我们可以使用动态规划的方法计算出字符串 s 的解码方法数。
具体地，设 f i 表示字符串 s 的前 i 个字符 s[1..i] 的解码方法数。在进行状态转移时，我们可以考虑最后一次解码使用了 s 中的哪些字符，那么会有下面的两种情况：
* 第一种情况是我们使用了一个字符，即 s[i] 进行解码，那么只要 s[i] !=0，它就可以被解码成 A∼I 中的某个字母。由于剩余的前 i−1 个字符的解码方法数为 f i−1，因此我们可以写出状态转移方程：
fi=fi−1,其中 s[i] !=0
* 第二种情况是我们使用了两个字符，即 s[i−1] 和 s[i] 进行编码。与第一种情况类似，s[i−1] 不能等于 0，并且 s[i−1] 和 s[i] 组成的整数必须小于等于 26，这样它们就可以被解码成 J∼Z 中的某个字母。由于剩余的前 i−2 个字符的解码方法数为 f i−2 ，因此我们可以写出状态转移方程：
fi=fi−2,其中 s[i−1] !=0 并且 10⋅s[i−1]+s[i]≤26
需要注意的是，只有当 i>1 时才能进行转移，否则 s[i−1] 不存在。
将上面的两种状态转移方程在对应的条件满足时进行累加，即可得到 fi 的值。在动态规划完成后，最终的答案即为 fn。
注意：动态规划的边界条件为：
f0 = 1
即空字符串可以有 1 种解码方法，解码出一个空字符串。
class Solution {
public:
int numDecodings(string s) {
int n = s.size();
vector<int> f(n+1);
f[0] = 1; //空字符串
for(int i=1;i<=n;i++){
if(s[i-1]!='0'){
f[i] += f[i-1];
}
if(i>1 && s[i-2]!='0' && ((s[i-2]-'0')*10 + (s[i-1]-'0')<=26 )){
f[i] += f[i-2];
}
}
return f[n];
}
};639 解码方法II
这里要分多种情况讨论。
因为这里总共两类，且每一类的情况很多，需要重复书写的地方也很多，故而可以采用两个函数，分别返回int值，这样就会显得简洁明了。而且便于更改。
class Solution{
private:
static constexpr int mod = 1000000007;
int check1(char ch){
if(ch=='0'){
return 0;
}
return ch == '*'?9:1;
}
int check2(char c0,char c1){
if (c0 == '*' && c1 == '*') {
return 15;
}
if (c0 == '*') {
return c1 <= '6' ? 2 : 1;
}
if (c1 == '*') {
if (c0 == '1') {
return 9;
}
if (c0 == '2') {
return 6;
}
return 0;
}
return c0 != '0' && (c0 - '0') * 10 + (c1 - '0') <= 26;
}
public:
int numDecodings(string s){
int n = s.size();
int a = 0, b = 1, c = 0;
// c 表示 f[i], b = f[i-1], a=f[i-2];
for (int i = 1; i <= n; ++i) {
c = (long long)b * check1(s[i - 1]) % mod;
if (i > 1) {
c = (c + (long long)a * check2(s[i - 2], s[i - 1])) % mod;
}
a = b;
b = c;
}
return c;
}
};