学步园

A message containing letters from A-Z is being encoded to numbers using
the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,

Given encoded message "12", it could be decoded as "AB" (1
2) or "L" (12).

The number of ways decoding "12" is 2.

思路：这道题跟走台阶有点类似，可以用dp做。不考虑边界条件时，假设已经编码xxxxxxxx_ _了i-1个数字，现在待编码第i个字符，从题意推导可得：设置num=s[i-1]*10+s[i]，如果num>=10&&num<=26，即s[i-1]s[i]可以编码成一个字符。用f[i]表示编码的方法数，i表示编码数字的下标，则f[i]+=f[i-2]；如果s[i]!='0'，则可以由i-1编码到i，则f[i]+=f[i-1]。

class Solution {
public:
    int numDecodings(string s) {
        int len = s.length(),i;
		vector<int> f;
		f.resize(len);
		for(i=0; i<len; ++i)
		{
			f[i] = 0;
		}
		if (len == 0)
		{
			return 0;
		}
		if (s[0] != '0')
		{
			f[0] = 1;
		}
		if (len == 1)
		{
			return f[0];
		}
		int num = (s[0] - '0')*10 + (s[1] - '0');
		if ((num > 10 && num < 20) || (num > 20 && num <= 26))
		{
			f[1] = 2;
		}
		if (num == 10 || num == 20 || (num > 26 && s[1] != '0'))
		{
			f[1] = 1;
		}
		if (len == 2)
		{
			return f[1];
		}
		for(i=2; i<len; ++i)
		{
			num = (s[i-1] - '0') * 10 + s[i] - '0';
			if (num >= 10 && num <= 26)
			{
				f[i] += f[i-2];
			}
			if (s[i] != '0')
			{
				f[i] += f[i-1];
			}
		}
		return f[len-1];
    }
};