题目难度：二星
考察点：动态规划

方法：动态规划

1.分析：

这是一道比较典型的动态规划问题，我们设dp[n]表示字符串前n个数字所有的解码方案，那么其实一共有26个英文字母，即对应着1-26这么多数字，而1-9是一位的，10-26是两位的，那么就存在如下两种情况：
a. 第n-2个数字和第n-1个数字组合起来的十进制数不超过26，那么此时dp[n] = dp[n-1] + dp[n-2]
b. 其它情况，dp[n] = dp[n-1]
所以有如下状态转移方程：

算法实现：
(1). 输入一个字符串s，初始化dp[0]=1。
(2). 遍历字符串，然后根据上述状态转移方程，求dp[n]
(3). 输出dp[s.size()]

2.复杂度分析：

时间复杂度：O(n) 
空间复杂度：O(n)

3.代码： 

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+5;
int dp[MAXN];
int main(){
    string s; cin>>s;
    dp[0] = 1;
    for(int i=1; i<=s.size(); i++) {
        if(i>=2 && s[i-2]=='1' || (s[i-2]=='2'&&s[i-1]<'7')) dp[i] = dp[i-1] + dp[i-2];
        else dp[i] = dp[i-1];
    }
    cout<<dp[s.size()]<<endl;
    return 0;
}