LeetCode 91. 解码方法

题目描述：
一条包含字母 A-Z 的消息通过以下方式进行了编码：
‘A’ -> 1
‘B’ -> 2
…
‘Z’ -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。

思路：
利用动态规划，
如果s[i]'0’的时候，做判断,如果s[i-1]‘1’||s[i-1]‘2’,f(n)=f(n-2)
反之返回0；
如果s[i]！='0’的时候，做判断,如果s[i-1]‘1’||s[i-1]==‘2’&&s[i]<=‘6’,f(n)=f(n-1)+f(n-2)
反之，f(n)=f(n-1)

代码如下：

class Solution {
public:
    int numDecodings(string s) {
        if(s.size()<1)  return 0;
        if(s.size()>=1&&s[0]=='0')   return 0;
        vector<int>dp(s.size()+1);
        dp[0]=1;
        dp[1]=1;
        for(int i=1;i<s.size();i++){
            if(s[i]=='0'){
                if(s[i-1]=='1'||s[i-1]=='2')
                dp[i+1]=dp[i-1];
                else return 0;
            }
            else{
                if(s[i-1]=='1'||(s[i-1]=='2'&&s[i]<='6'))
                dp[i+1]=dp[i]+dp[i-1];
                else dp[i+1]=dp[i];
            }
        }
        return dp[s.size()];
    }
};