leetcode 91 Decode Ways

https://www.cnblogs.com/grandyang/p/4313384.html

动态规划，如果当前数字不为0，则当前数字可以单独转换，有dp[i-1]种方法（dp[i-1]的每一种方法都加上当前的转换）；如果和前面一个数字组成的数字大于0，小于27，s[i-2]和s[i-1]可以转换，有dp[i-2]种方法（dp[i-2]中的每一种方法都加上这个转换）。

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