思路：动态规划的思路
首先是加入一个字符，如果第一个字符就为0直接返回0；
dp[0]=1;
如果第二个字符不为0，需要判断是否和前一个字符组成一个数字（在10-27的范围）如果组成则dp[i]=dp[i-1]+dp[i-2]
如果不能组成，则dp[i]=dp[i-1]
代码如下：
class Solution { public: int numDecodings(string s) { int length=s.length(); vector<int>res(length); //如果开始第一个为0或者字符串为空则返回0 if(s[0]=='0'||length==0)return 0; //第一个字符不为0的情况下肯定是1种组成方案 res[0]=1; for(int i=1;i<length;i++){ //如果当前字符不为0，首先不管能不能跟前一个字符组成都相等于前一个字符 if(s[i]!='0') res[i]=res[i-1]; //计算与前一个字符组成的值，假设前一个字符为0，也就说明组成的字符<10 int num=stoi(s.substr(i-1,2)); //如果可以组成数字 if(num>9&&num<27){ //前两个字符组成数字，则直接+1=2 if(i==1){ res[i]++; //如果当前字符与前一个字符组成字符串，则相当于两种情况 前i-1个字符+i单个字符和前i-2个字符+i-1、i两个字符组成的方案数 }else{ res[i]+=res[i-2]; } } } return res[length-1]; } };
