decode-ways

设定状态为：f[i]表示s从0开始，长度为i的子串的解码方式数量，于是我们最终要求的答案便是f[n]。

那么如何求解f[i]呢？这个很简单，枚举最后一个字母对应1位还是2位，将f转化为规模更小的子问题。

设f[i] = 0
枚举最后一个字母对应1位（要求s[i - 1] != '0')，那么有f[i] += f[i-1]；
枚举最后一个字母对应2位（要求i > 1且s[i - 2]和s[i - 1]组成的字符串在"10"~"26"的范围内），那么有f[i] += f[i - 2]；
也就是说，我们可以通过f[i - 1]和f[i - 2]计算出f[i]来，这就是我们的状态和转移方程。

在具体实现中，我们可以按照i从1到n的顺序，依次计算出所有的f[i]。

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