91. Decode Ways

91. Decode Ways

已知：

‘A’---1

‘B’--2

 ...

'Z'--26

给出一个字符串例如“12”则有可能是当作“AB”（1   2）也有可能是“L”（12）故一共有2中看法。

思路，很明显这是一个多层次影响求单值问题，可以采用动态规划：引入数组dp[i]表示s0,s1,...si-1这样前i个字符求法个数，注意字符串s每一位都有可能取值‘0-9’

1 当当前位s[i-1]=='0'：

       若前一位s[i-2]=='1'||s[i-2]=='2'则s[i-2]s[i-1]一定是在一起这一种解法，故dp[i]=dp[i-2]

       否则不满足转换原则，直接返回0

2 否则，如果前面数字为1或者前面数字为2且当前数字在1~6之间，说明都可以进行2种编码（分开dp[i-1]或者和在一起dp[i-2]），因此dp[i] = dp[i-1] + dp[i-2]；

3 其他情况，当前数字必须单独进行编码转换，因此dp[i] = dp[i-1]

int numDecodings(string s){
int n=s.size();
if(n<1||s[0]=='0')return 0;

for(int i=0;i<n-1;i++)
    if(s[i]=='0'&&s[i+1]=='0')return 0;
vector<int>dp(n+1);
dp[0]=1;
dp[1]=1;
for(int i=2;i<=n;i++)
{if(s[i-1]=='0'){
    if(s[i-2]=='1'||s[i-2]=='2')dp[i]=dp[i-2];
    else return 0;
		 }
 else if(s[i-2]=='1'||(s[i-2]=='2'&&(s[i-1]>='1'&&s[i-1]<='6')))dp[i]=dp[i-1]+dp[i-2];
 else dp[i]=dp[i-1];
}
return dp[n];
}