[leetcode-91-Decode Ways]

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[i],那么再在末尾加入一个字符的话，则仅需考虑当前字符与上一个字符的情况，容易想到使用动态规划：

1.当前数字如果能够与上一个数字组成一个字符（即小于或等于26）那么说明当前能够组成的组合数dp[i] = dp[i-1]+dp[i-2];

   （dp[i-1]为最后一位数字组成字符的时候，dp[i-2]为最后两位组成一个字符的时候）

2.当前数字如果不能够与上一个数字组成一个字符（比如上一个数字为3此时的数字为2，则组成32，不能找到对应字母），

      则dp[i] = dp[i-1];(即最后一位只能转化为唯一的字符)

3.需要注意的就是数字0的情况，0不能出现在首位，而且0不能单独转化为一个字母，必须考虑0之前的字符情况，

     比如上一个数字为3此时的数字为0，则此时不可能转化成字母。但是如果是20就可以了，于是做一个处理就是将dp[i-1]置为0，这样就能够满足了。

int numDecodings(string s)
    { 
        int size = s.size();
        if (size == 0 || s[0] == '0')return 0;
        vector<int> dp(size+1,0);
        dp[0] = dp[1] = 1;

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

        return dp[size];
    }

参考：

http://www.cnblogs.com/jdneo/p/5338983.html